수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 에 시작해서 에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
첫 번째 줄에 N이 주어진다. ()
이후 N개의 줄에 가 주어진다. ()
강의실의 개수를 출력하라.
1374 강의실 이 문제와 입력 값만 살짝 다른 같은 문제이다.
수업 시간 시작 시간, 끝나는 시간이 주어지며 이 값들을 수업 시작 시간으로 정렬해둔다.
rooms 리스트를 이용해 최대한 적은 수의 강의실을 사용하도록 했다. 여기에 첫 수업 끝나는 시간을 미리 저장해 둔다.
for 문을 돌면서 다음 수업 시작 시간이 현재 끝나는 시간보다 작거나 같을 때에만 기존 수업을 끝내고(heappop) 다음 수업을 추가(heappush)시킨다.
아직 빈 강의실이 없을 때에는 새롭게 강의실을 추가(heappush)해준다.
따라서 rooms 리스트의 길이가 강의실의 개수가 된다.
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
lesson = sorted([list(map(int, input().split())) for _ in range(int(input()))])
rooms = [lesson[0][1]]
for start, end in lesson[1:]:
# 수업이 끝난 직후에 다음 수업을 시작할 수 있다.
if rooms[0] <= start:
heappop(rooms)
heappush(rooms, end)
# 지금 하는 수업 종료 시간보다 다음 수업 시작 시간이 더 빠를 경우
else:
heappush(rooms, end)
print(len(rooms))