#1931 : 회의실 배정

풀이방법

사용된 것:

Comparator

두 개의 변수를 기준으로 비교하기 위하여 Comparator를 직접 Override하였다.

그리디 알고리즘

선택 가능한 회의들 중 무조건 제일 일찍 끝나는 것부터 고르는 게 최선의 선택이다.

따라서 그리디 알고리즘에 적합하다.

 

2022.02.14

오답노트 #1931 : 회의실 배정

입력값으로 제공된 회의들을 먼저 끝나는 시간 기준으로 오름차순 정렬한다.

끝나는 시간이 같은 회의들끼리는 시작하는 시간 기준으로 오름차순 정렬한다.

이렇게 정렬된 리스트를 앞에서부터 방문하며, 다음과 같은 방식으로 시간표에 차례차례 추가하면 된다.

 

회의를 하나 추가할 때마다, 시간표에 추가된 회의 중 가장 마지막 회의의 끝나는 시간을 정수 타입 변수 prevEnd에 저장해줄 것이다.

일단 리스트의 가장 앞에 있는(끝나는 시간이 가장 이른) 회의를 시간표에 추가한다.

 

현재 prevEnd 값은 리스트 상 첫번째 회의의 종료시간이다.

 

리스트의 두 번째 회의의 시작시간이 prevEnd보다 이르다면, 회의시간이 겹치므로 이 회의는 시간표에 추가할 수 없다. 세 번째 회의로 넘어간다.

 

그러나 만약 두 번째 회의의 시작시간이 prevEnd와 같거나 그보다 늦다면, 회의시간이 서로 겹치지 않으므로 시간표에 추가할 수 있다. 즉, 이 경우 두 번째 회의는 시간표에 추가할 수 있는 모든 회의들 중 최적의(가장 일찍 끝나는) 선택이다. 그러므로 두 번째 회의를 시간표에 추가하고 prevEnd의 값을 두 번째 회의의 종료시간으로 바꾸어주어야 한다.

 

이 과정을 리스트의 마지막 회의까지 반복하면서, 회의를 시간표에 추가할 때마다 카운트를 1 증가시켜주면 된다.

리스트를 끝까지 탐색한 후 카운트 값을 화면에 출력한다.

 

코드

Java(2022.02.14)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		Meeting[] meets = new Meeting[n];
		
		//회의들의 정보 읽어오기
		for(int i = 0; i<n; i++) {
			String[] input = br.readLine().split(" ");
			meets[i] = new Meeting(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
		}
		//Comparator Overriding
		Comparator<Meeting> cp = new Comparator<Meeting>() {

			@Override
			public int compare(Meeting o1, Meeting o2) {
				// TODO Auto-generated method stub
				int st1 = o1.start;
				int st2 = o2.start;
				int end1 = o1.end;
				int end2 = o2.end;
				
				//먼저 end를 기준으로 오름차순 정렬
				if(end1>end2)return 1;
				if(end1<end2)return -1;
				
				//end가 서로 같은 객체끼리는
				else{
					//start를 기준으로 오름차순 정렬
					if(st1>st2)return 1;
					else return -1;
				}
			}
			
		};
		//정렬하기
		Arrays.sort(meets,cp);
		//답 구하기
		int prevEnd = 0;
		int cnt = 0;
		for(int i = 0; i<n; i++) {
			if(prevEnd<= meets[i].start) {
				cnt++;
				prevEnd = meets[i].end;
			}
		}
		//답 출력
		System.out.print(cnt);
	}

}

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