문제
N개의 강의 시간표가 주어질 때, 모든 강의를 진행하기 위한 최소 강의실 수를 구하라.
입력
첫째 줄에 N, 이후 N줄에 (번호, 시작, 종료)가 주어진다.
출력
필요한 최소 강의실 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 1 3 2 2 4 3 3 5 | 2 |
풀이
강의를 시작 시간순으로 정렬하고, 종료 시간을 최소 힙으로 관리하여 강의실을 재사용한다.
- 강의를 시작 시간 기준으로 우선순위 큐에 넣는다
- 종료 시간 관리용 최소 힙(rooms)을 준비한다
- 각 강의에서 현재 종료된 강의실을 제거하고, 새 종료 시간을 추가한다
- rooms의 최대 크기가 필요한 강의실 수이다
핵심 아이디어: 종료 시간 최소 힙으로 가장 빨리 끝나는 강의실을 재사용한다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day465BOJ1374강의실 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
PriorityQueue<Integer> rooms = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int[] lecture = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()) };
pq.offer(lecture);
}
int ans = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
while (!rooms.isEmpty() && rooms.peek() <= cur[1]) {
rooms.poll();
}
rooms.offer(cur[2]);
ans = Math.max(ans, rooms.size());
}
System.out.print(ans);
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)