문제
N개의 수업이 시작 시간과 종료 시간으로 주어졌을 때, 모든 수업을 진행하기 위해 필요한 최소 강의실 수를 구하라. 한 수업이 끝나는 시간에 다른 수업을 바로 시작할 수 있다.
입력
첫째 줄에 N (1 이상 200,000 이하), 둘째 줄부터 N개의 줄에 시작 시간과 종료 시간이 주어진다.
출력
필요한 최소 강의실 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 3 2 4 3 5 | 2 |
풀이
시작 시간 기준으로 정렬한 뒤, 우선순위 큐로 강의실 종료 시간을 관리한다.
- 수업을 시작 시간 기준으로 오름차순 정렬한다 (같으면 종료 시간순)
- 우선순위 큐(최소 힙)에 첫 수업의 종료 시간을 넣는다
- 다음 수업부터 순회하며, 큐의 최솟값(가장 빨리 끝나는 강의실)과 현재 수업의 시작 시간을 비교한다
- 시작 시간이 최솟값 이상이면 기존 강의실을 재사용할 수 있으므로 큐에서 꺼낸다
- 현재 수업의 종료 시간을 큐에 넣는다
- 최종 큐의 크기가 필요한 최소 강의실 수이다
핵심 아이디어: 가장 빨리 끝나는 강의실부터 재사용을 시도하면 항상 최적이다. 재사용이 불가능하면 새 강의실이 필요하므로 큐 크기가 증가한다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day306BOJ11000강의실배정 {
public static void main(String[] args) throws Exception {
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[0] - o2[0] == 0)
return o1[1] - o2[1];
return o1[0] - o2[0];
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(arr[0][1]);
for (int i = 1; i < arr.length; i++) {
if (arr[i][0] >= pq.peek()) {
pq.poll();
}
pq.add(arr[i][1]);
}
System.out.println(pq.size());
br.close();
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)