[Java] 백준 19598 최소 회의실 개수

https://www.acmicpc.net/problem/19598

난이도

골드 5

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

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

출력

첫째 줄에 최소 회의실 개수를 출력한다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] meetings = new int[N][2];
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i][0] = Integer.parseInt(st.nextToken()); // start
            meetings[i][1] = Integer.parseInt(st.nextToken()); // end
        }

        // 1. 시작 시간 기준 정렬
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        // 2. 끝나는 시간만 저장하는 우선순위 큐
        PriorityQueue<Integer> room = new PriorityQueue<>();
        room.add(meetings[0][1]); // 첫 회의 끝나는 시간

        for(int i = 1; i < N; i++){
            if(room.peek() <= meetings[i][0]){
                room.poll(); // 가장 먼저 끝나는 회의실을 재사용
            }
            room.add(meetings[i][1]); // 새 회의 배정
        }

        System.out.println(room.size()); // 큐의 크기 = 회의실 개수
    }
}

처음에는 회의가 끝나는 시간을 기준으로 pq에 넣어서 코드를 작성했었는데 답이 틀렸다.

다시 생각해보니,

1. 회의를 시작 시간 순으로 정렬
2. 회의실마다 끝나는 시간을 관리하는 우선순위 큐(min heap)를 사용
3. 현재 회의 시작시간 >= 가장 빨리 끝나는 회의실 시간이라면 해당 회의실 재사용이 가능하므로 큐에서 제거하고, 새 회의 끝나는 시간 넣음
4. 그렇지 않으면 새 회의실을 하나 추가

방식으로 짜야 맞는 것 같다.