그리디, 탐욕 알고리즘

완전검색(브루트포스)를 사용했을 때 n>=30일 경우 너무 많은 시간을 소비하기 때문에 그리디 알고리즘(내가 생각하는 최적의 해)를 구하기 위해 효율적인 방법으로 접근

단, 최적의 해를 반드시 구한다는 보장이 없을 수 있다.

package com.ssafy.w0817;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

//Greedy, 탐욕 알고리즘
public class MeetingRoomTest_Greedy {

	static class Meeting implements Comparable<Meeting> { // 미팅객체들을 비교하며 판단하기 위해 Comparable 사용
		// Comparable : 원소 스스로가 다른 원소랑 자신을 비교하는 것
		int start, end;

		public Meeting(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		//일단 오름차순으로 종료시간 정렬
		@Override
		public int compareTo(Meeting o) { // 대소 비교 
			
			//오름차순 일 때...//내림차순은 반대로
			//음수 -> 내가 작다. --->그대로
			//0 -> 둘이 같다.		--->그대로
			//양수 -> 내가 크다. ---> 교환
			//주의할점 : 둘 다 음수 일 경우 오버플로우 조심 (여기서는 둘다 양수이므로 상관 X)
			
			int value = this.end - o.end;
			if(value != 0) return value;	//종료시간이 다르면
			
			//종료시간이 같다면 시작시간이 빠른 순서로.
			return this.start - o.start;
		}

		@Override
		public String toString() {
			return "Meeting [start=" + start + ", end=" + end + "]";
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); 	//회의 개수
		
		Meeting [] meetings = new Meeting[N];
		for(int i=0; i<N; i++) {
			meetings[i] = new Meeting(sc.nextInt(), sc.nextInt());
		}
			
			//출력해서 미팅 확인해보기
			for(Meeting meeting : getSchedule(meetings)) {
				System.out.println(meeting);
			}
			
	}
	
	//전체 회의정보를 받아 배치가능한 최대 회의를 arraylist에 담는다.
	static ArrayList<Meeting> getSchedule(Meeting [] meetings){
		
		ArrayList<Meeting> list = new ArrayList<>();
		Arrays.sort(meetings);	// 종료시간 기준 오름차순 정렬
		list.add(meetings[0]);		//첫회는 무조건 일단 추가하기
		
		//두번째 회의부터 보기
		for(int i=1, size = meetings.length; i < size; i++) {
			
			//이전회의 종료시간이 내가 담을려고 하는 회의의 시작시간과 겹치지 않을 경우 담기
			if(list.get(list.size()-1).end <= meetings[i].start)	{//마지막회의의 종료시간 <= 내가 담으려고 하는 회의의 시작시간
				list.add(meetings[i]);
				
			}
		}
		return list;
		
	}

}