백준 1931번 - 회의실 배정

문제

백준 1931번 - 회의실 배정

아이디어

• 회의가 최대한 겹치지 않도록 해야 회의의 최대 개수를 구하는데 유리할 것이다.
• 회의를 종료 시간 순으로 정렬한다. 종료 시간이 같으면 시작 시간 순으로 정렬한다. 왜냐하면 회의의 시작시간과 끝나는 시간이 같을 수도 있다라는 조건이 있는데 예를 들어 (2, 2), (1, 2)일 때 두 회의 모두 겹치지 않고 가능한데 (2, 2)를 먼저 계산하면 겹치는 강의로 판단하기 때문이다.
• 종료 시간 순으로 정렬이 되었기 때문에 회의를 순차적으로 탐색하면서 회의의 시작 시간이 이전 회의의 종료 시간 이상이면 겹치지 않는 회의로 카운팅한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N log N)

코드 구현

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

public class BJ_1931 {
    public static void main(String[] args) throws 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, (o1, o2) -> {
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });

        int count = 0;
        int end = -1;

        for (int[] a : arr) {

            if (a[0] >= end) {
                end = a[1];
                count++;
            }
        }

        System.out.println(count);
    }
}