[Python] 강의실 배정 - 백준 (그리디)

해당 글은 백준 11000번 문제 '강의실 배정'을 다룬다.

문제

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

11000번: 강의실 배정

 

설명

해당 문제는 우선순위 큐를 사용해서 항상 최솟값이 인덱스 0 자리에 위치하게하고, pop할 때도 최솟값이 삭제되도록 한다. 즉, 비교대상은 항상 우선순위 큐에 포함된 최솟값이다. 큐에 저장된 회의 끝나는 시간과 비교하여 현재 회의 시작 시간보다 크다면, 현재 회의 끝나는 시간을 큐에 push 한다.

아니라면 큐에 있는 값을 pop하고, 현재 회의 끝나는 시간을 큐에 push 한다.

최종적으로 큐에 남아있는 갯수가 강의실의 갯수가 된다.

 

 

코드

import heapq, sys
input = sys.stdin.readline
n = int(input())
time = []
for _ in range(n):
    time.append(list(map(int, input().split())))
time.sort()

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