[BOJ] 회의실 배정 # 1931

회의실 배정

그리디 알고리즘의 대표적인 문제 회의실 배정을 풀이했다. 그리디 알고리즘 처음 쓴다.

처음 제출했을 때, 틀린 이유는
'회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.'라는 조건 때문이다.

8 8
3 8

위와 같이 입력이 들어왔을 때, (8, 8)의 회의가 먼저 시작된다면 (3, 8)의 회의는 배정될 수 없다. 하지만 회의가 끝나는 시간이 같을 때, 시작하는 시간을 기준으로 정렬한다면 (3, 8)과 (8, 8) 회의 모두 배정될 수 있다.

Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				return o1[1] - o2[1];
			}
		});

그래서 Comparator를 선언할 때, 위와 같이 회의 시작하는 시간이 같을 때의 정렬 조건도 추가해줘야 한다.

전체 코드

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

public class Main_1931 {
//	S1 회의실 배정
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int arr[][] = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				return o1[1] - o2[1];
			}
		});
		int cnt = 0;
		int f = 0;
		for (int i = 0; i < N; i++) {
			if(f <= arr[i][0]) {
//				System.out.println(arr[i][0] + " " + arr[i][1]);
				f = arr[i][1];
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}