[Java] 백준 11000번 강의실 배정

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

풀이

선생님이 최소의 강의실을 사용해서 모든 수업을 할 수 있게 만들어야 한다.

시작 시간 기준으로 강의를 정렬하고, i번째 강의가 먼저 시작했던 강의 중 가장 빨리 끝나는 강의의 바로 뒤에 배정될 수 있는지 보면 된다. (그리디)
만약 배정될 수 없다면 새로운 강의실에서 강의해야 한다.

예를 들어 K번 강의실에 배정된, 가장 빨리 끝나는 j번째 강의가 있다. 현재 i번째 강의의 강의실을 배정하려고 한다.
j번째 강의의 종료 시간을 Tj이라고 하고, i번째 강의의 시작 시간을 Si라고 하자.

• Tj <= Si 일 때
  K번 강의실에서 j번째 강의 후 i번째 강의 진행 가능

• Tj > Si 일 때
  K번 강의실에서 j번째 강의 후 i번째 강의 불가능 -> i번째 강의는 새로운 강의실에 배정

이때 "가장 빨리 끝나는 j번째 강의"를 구하기 위해, 우선순위 큐를 이용해 min heap을 구현했다.

min heap에 각 강의실에서 가장 늦은 강의의 종료 시간을 저장하면, 마지막에 min heap의 크기가 강의실의 최소 개수이다.

코드

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws Exception {
		int ans = 0;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int[][] schedule = new int[N][2];
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            schedule[i][0] = Integer.parseInt(st.nextToken());
            schedule[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(schedule, (x, y) -> (x[0] - y[0]));
        
        // min heap
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(schedule[0][1]); // 끝나는 시간
        
        for(int i=1; i<N; i++) {
            if(pq.peek() <= schedule[i][0]) {
                pq.poll();
            }
            pq.offer(schedule[i][1]);
        }
        
        System.out.println(pq.size());
	}
}