[백준] 11000. 강의실 배정

[백준] 11000. 강의실 배정 - 파이썬

https://www.acmicpc.net/problem/11000

 

풀이

Greedy를 생각하며.. 힙을 이용해 품.

강의를 모두 순회하며 강의의 종료시간을 최소 힙에 집어넣는데,

최소 힙의 root(제일 빠른 종료시간) > 처리할 강의의 시작시간

이면 그대로 최소 힙에 처리할 강의의 종료시간을 넣고(강의실을 +1)

아니라면, 그 강의실에서 계속 강의해도 되니까

최소 힙에서 pop하고 다시 새로운 종료시간을 넣음.

 

import heapq
import sys

read = sys.stdin.readline

N = int(read().strip("\n"))
lec = [list(map(int, read().strip("\n").split())) for _ in range(N)]

lec.sort()

# priorityQueue에는 종료시간을
q = []
heapq.heappush(q, lec[0][1])

for l in lec[1:]:
    if q[0] > l[0]:
        heapq.heappush(q, l[1])
    else:
        heapq.heappop(q)
        heapq.heappush(q, l[1])

print(len(q))