[백준] 11000번 - 강의실 배정 Python

문제

---

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

김종혜 선생님한테는 $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$)

출력

---

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

예제 입력 1

---

3
1 3
2 4
3 5

예제 출력 1

---

2

풀이

---

Python

import sys
import heapq as hq
input = sys.stdin.readline

n = int(input().rstrip())
c = [tuple(map(int,input().rstrip().split())) for _ in range(n)]
c.sort()
heap = []
hq.heappush(heap, c[0][1])

for i in range(1, n):
    if c[i][0] < heap[0]:
        hq.heappush(heap, c[i][1])
    else:
        hq.heappop(heap)
        hq.heappush(heap, c[i][1])

print(len(heap))

정리

---

• 입력으로 들어온 $S_i$, $T_i$를 $S_i$를 기준으로 오른차순 정렬한다.
• 첫 번째 강의를 기준으로 시작하므로 첫 번째 강의의 끝나는 시간을 우선순위 큐에 추가한다.
• 첫 번째 인덱스부터 $S_i$의 값이 우선순위 큐의 첫 번째 값보다 작으면 강의실을 하나 추가해야하기 때문에 우선순위 큐에 추가한다.
• 반대의 경우(클 경우) 우선순위 큐에서 첫 번째 값을 제거하고 $T_i$ 값을 우선순위 큐에 넣는다(한 강의실에서 이어지는 강의의 끝나는 시간을 넣음).