[Softeer Lv.3] 강의실 배정 (Python)

문제

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다. 

제약조건

1 ≤ N ≤ 106 인 정수
1 ≤ Si ＜ Fi ≤ 109

입력형식

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다.

출력형식

첫 번째 줄에 최대 강의 수를 출력하라.

입력예제1

3
1 3
2 4
3 5

출력예제1

2

 

✔️ Code 

import sys
import heapq
input = sys.stdin.readline

heap = []
n = int(input())
for _ in range(n):
    s, f = map(int, input().split())
    heapq.heappush(heap, (f, s)) # 끝나는 시간 순으로 우선순위 정렬됨

x = 0
cnt = 0
while heap:
    f, s = heapq.heappop(heap)
    if s >= x: # 시작시간이 이전의 끝나는 시간보다 크거나 같다면
        x = f
        cnt += 1

print(cnt)

✏️ Comment

맨날 까먹는 문제.. 이제 확실히 어떤 식으로 풀어야하는지 알 것 같다.

여기서는 시간초과 때문에 우선순위큐인 heapq를 사용했다. (끝나는 시간, 시작 시간) 순으로 오름차순 정렬해서 우선순위큐에 저장이 되고 하나씩 꺼내면서 시작 시간이 이전의 끝나는 시간보다 크거나 같으면 강의 수를 더해주고 끝나는 시간을 시작 시간으로 바꿔주는 것을 heap이 있을 동안 반복하면 된다.