백준 11000번: 강의실 배정 파이썬 코드(우선순위 큐)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

import heapq
import sys

n = int(sys.stdin.readline())

heap = []
q = []
count = 0
for _ in range(n):
    start, end = map(int,sys.stdin.readline().split())
    heapq.heappush(heap, [start,end])

start, end = heapq.heappop(heap)
heapq.heappush(q, end)
while heap:
    start, end = heapq.heappop(heap)
    if q[0] <= start:
        heapq.heappop(q)
    heapq.heappush(q, end)

print(len(q))

설명

해당 블로그의 백준 1374번과 설명이 유사하다.

 

두 개의 힙큐를 만들어 준 다음, 강의실의 시작시간과 끝나는 시간과 번호를 힙큐(heap)에다가 넣어주고, 다른 힙큐(q)에다가 힙큐(heap)를 pop해서 끝나는 시간을 넣어준 다음, while문을 돌리면서 힙큐(q)와 힙큐(heap)에서 pop 한 시작 시간을 비교해주면서 시작시간이 힙큐(q)에서 뽑은 값보다 늦이면 힙큐(q)를 pop해준다. 힙큐(q)에다가 힙큐(heap)에서 pop한 끝나는 시간을 다시 push해주는 것을 힙큐(heap) 원소가 다 빠질 때까지 반복한다.

 

heap은 그냥 강의실을 시작시간 기준으로 정렬해놓는 힙큐이고, q는 진행중인 강의 중 끝나는 시간이 가장 이른 것을 뽑아준다고 보면 된다.