11000 강의실 배정

🥇 11000 강의실 배정

문제

---

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

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

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

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

입력

---

첫 번째 줄에 N이 주어진다. ($1 ≤ N ≤ 200,000$)

이후 N개의 줄에 $S_i, T_i$가 주어진다. ($0 ≤ S_i < T_i ≤ 10^9$)

출력

---

강의실의 개수를 출력하라.

분석

---

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))