[백준1931번] 회의실배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

나의 풀이

그리디 알고리즘을 사용하는 문제로 처음에는 회의를 진행하는 시간이 작은 것들을 많이 넣으면 될까 생각을 하고 주어지는 두 시간들의 차이를 배열에 저장하고 정렬을 한 뒤 어떻게 해보려했다... 하지만 역시나 안됐다. 그래서 생각을 해보니 회의의 종료시간이 빠른 것부터 넣어가다보면 될 것같았다. 그래서 주어지는 회의 시간들을 종료되는 시간을 기준으로 정렬을 하고 시작시간을 비교하여 최대의 개수를 구했다. 이렇게 코드를 짜니까 예제로 주어지는 문제는 풀려서 답안 제출을 해보니 채점이 진행되다가 '틀렸습니다'가 나와 한참동안 또 생각에 잠겼었다. 알고보니 역시나 종료시간이 같을때가 문제였다. 가령 예를 들어보면 다음과 같다.

2 2
0 2
1 2
이렇게 배열이 정렬이 되었다고 친다면 앞에서 짠 코드로는 '2 2'에서만 카운트가 되고 뒤에 '0 2,1 2'는 무시가 될 것이다. 결과적으로 count는 1이 증가한다.
그러나 아래와 같다면?
0 2
1 2
2 2
이렇게 정렬이 된다면 count는 2가 증가한다. 왜냐하면 '0 2'에서 카운트가 증가하고 '1 2'는 무시하고나서 '2 2'에서 카운트가 증가하기때문이다.

따라서 회의시간을 정렬할때 뒤에 종료시간으로만 정렬을 하면 안되고 종료시간이 같다면 시작시간을 기준으로 또 정렬을 해야한다.

코드

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

/**
 * 1931번 회의실배정
 */
public class Baeckjun1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] meeting = new int[n+1][2];
        int endtime = 0;
        int count = 0;

        StringTokenizer st = null;
        for (int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            meeting[i][0] = Integer.parseInt(st.nextToken());
            meeting[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(meeting, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                if (ints[1] == t1[1])
                    return ints[0] - t1[0];
                else
                    return ints[1] - t1[1];
            }
        });

        for (int i=1; i<=n; i++) {
            if (endtime <= meeting[i][0]) {
                endtime = meeting[i][1];
                count += 1;
            }
        }

        System.out.println(count);
    }
}