[백준] 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))