[11000] 강의실 배정

😲 문제

출처
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

입력
3
1 3
2 4
3 5

출력
2

❗️ 문제 재정의

문제를 보자마자 유명한 문제인 "회의실 배정" 문제가 떠올랐다.
때문에 바로 그리디하게 접근할 수 있었다.

문제의 조건을 좀 더 간략화해보자.
먼저 한 수업의 종료시간이 다음 수업의 시작시간보다 작거나 같아야한다.
i의 end가 j의 start보다 작아야하는 것이다.

✔ 계획 수립

heap 으로 접근해보자. 어차피 필요한건 가장 작은 종료시간이다.
먼저 주어진 입력 시작, 종료 시간들을 시작시간으로 정렬시킨다. (강의의 시작은 시작시간에 의해 순차적으로 진행되기에)
다음은 종료시간을 heap에 넣어가며 다음 시작시간과 비교하면 된다.
(먼저 한 수업의 종료시간이 다음 수업의 시작시간보다 작거나 같은지 검사)
다음 수업과 연속적으로 이어나가진다면 즉, 겹침이 없다면 다른 강의실을 잡지 않아도 된다.

👨🏻‍💻 문제 풀이

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

n = int(input())
schedule = [list(map(int, input().split())) for _ in range(n)]
schedule.sort()

room = []
for start, end in schedule:
    if room and start >= room[0]:
        heappop(room)
    heappush(room, end)
    
print(len(room))

😅 회고

바로 heap을 떠올리는 것은 약간 어려웠다.
조건에 필요한 것들을 순차적으로 정리해나갔더니 문제가 풀렸다.

1. 그리디한 문제이다.
2. 먼저 한 수업의 종료시간이 다음 수업의 시작시간보다 작거나 같은가 를 검사해야한다.
3. 회의실의 수는 마지막 종료시간의 개수로 볼 수 있다.