강의실 배정 [백준 11000] (파이썬)

문제

---

강의실 배정 [백준 11000]
https://www.acmicpc.net/problem/11000

풀이

---

처음에 끝나는 시간들을 반복문으로 통해서 리스트에 추가하고, 그 리스트를 순차 탐색하며 입력값의 끝나는 시간과 비교해 바꿔주는 형식의 코드를 짰는데 이중 반복문이고 n의 크기가 커서 시간 초과가 나왔다.
그래서 이용한 게 heapq 이다. 먼저 입력값들을 시작하는 시간으로 정렬을 해주고, 첫번째 입력값의 끝나는 시간을 힙큐에 넣는다.
다음 인덱스부터 heapq의 처음 값 즉 가장 빨리끝나는 시간과 입력값의 시작하는 시간과 비교하여서 만약 가장 빨리 끝나는 시간이 더 크면 강의실이 더 필요한 거니까 heapq 에 추가, 아닌 경우, 즉 강의실이 더 필요하지 않은 경우엔 가장 빨리 끝나는 값을 버리고 해당 입력값의 끝나는 시간을 힙에 추가해준다.
마지막으로 힙의 길이가 강의실의 개수가 된다.

코드

---

import heapq
n = int(input())
time = [list(map(int, input().split())) for _ in range(n)]
time.sort(key = lambda x : x[0])
q = []
heapq.heappush(q, time[0][1])

for i in range(1, n):
    if q[0] > time[i][0]:   
        heapq.heappush(q, time[i][1])
    else:
        heapq.heappop(q)
        heapq.heappush(q, time[i][1])
print(len(q))