문제
접근
이전의 회의실 배정 문제와 비슷해보인다.
비슷해보이긴 하지만, 회의실 배정의 경우 최대한 많은 회의를 하도록 하는게 목표였다면,
이번에는 모든 강의를 진행해야 한다.
그 때 필요한 강의실을 최소화하는게 목표이다.
즉, 겹친다고 버릴 수 없다.
처음에는 쉽게 생각하고 강의실 배정 문제와 비슷하게 해결하려 했다.
하지만 시간초과 때문에 더 효율적인 방법을 찾아야 했다.
결국 모든 강의를 진행해야 하므로, 시작 시간을 기준으로 정렬했다.
현재 강의를 시작해야 하는 시점에 강의실이 꽉 차 있으면, 결국 강의실을 하나 더 배정해줘야 하므로.
그리고 우선순위큐를 만들었다.
현재 존재하는 강의실을 모두 순회하며 확인하려면 시간이 오래걸린다.
최악의 경우 n번째 강의를 확인해야 하는 시점에서 강의실이 n-1개 있다면, n-1개를 모두 순회할 순 없다.
저런 경우가 반복되면 최악의 경우 n^2이다.
우선순위큐는 강의가 끝나는 시점을 기준으로 생성했다.
꼭 빨리 끝난 강의실에 배정해야 하는 것은 아니지만, 강의실이 비어있는지 체크하는 과정에서 가장 빨리 끝나는 강의가 아직 안끝났다면 뒤는 더 이상 볼 필요가 없다.
즉 강의실에 배정할 수 있는지, 아니면 강의실을 늘려야하는지 확인하는 과정을 O(1)에 처리할 수 있다.
이렇게 하고 배열을 순서대로 돌면서 강의실이 비었으면(가장 빨리 끝나는 강의 시간이 현재 강의의 시작시간보다 빠른 경우),
해당 강의 종료 시간을 현재 강의의 종료시간으로 교체한다.
빈 강의실이 없다면 현재 강의의 종료시간으로 강의실을 하나 늘린다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
import heapq
input = sys.stdin.readline
def findRoom(room, start):
for idx, item in enumerate(room):
if start >= item:
return idx
return -1
n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]
arr = sorted(arr, key = lambda x:(x[0], x[1]))
scheduler = [0]
for start, end in arr:
if scheduler[0] <= start:
heapq.heappop(scheduler)
heapq.heappush(scheduler, end)
else:
heapq.heappush(scheduler, end)
print(len(scheduler))