[Python] BOJ/백준 11000번 강의실 배정

[문제]

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

11000번: 강의실 배정

 

[풀이]

문제의 핵심은 현재 수업의 종료 시간이 다음 수업의 종료 시간보다 늦을 경우 회의실 하나를 더 배정해야 한다.

 

먼저 수업의 시작과 끝 시간을 queue에 넣고 이를 정렬하면 시작 시간이 가장 빠른 수업이 가장 앞에 오게 되기 때문에 첫 수업의 종료시간을 새로운 큐인 room에 넣는다.

1. 두 번째 수업부터 첫 번째 회의와 비교를 하는데
   두 번째 수업의 시작시간 < 첫 수업의 종료시간 일 경우
   강의실을 새로 배정해야 하고 그렇지 않을 경우 기존 강의실을 사용해도 된다.
2. 진행하고 있는 수업의 시작시간 > 진행할 수업의 종료시간 일 경우
   기존 강의실을 사용하기 때문에 room에서 진행하고 있던 수업을 pop한 후 새로운 강의시간을 push 한다.
3. 새로 강의실을 개설해야 할 경우, room에 새로운 강의의 종료시간을 push 한다.

이 때 종료시간이 빠른 강의실부터 다음 회의를 이어서 개최해야 하기 때문에

우선순위 큐를 이용해 큐에 push를 해주어 큐가 정렬상태를 유지할 수 있도록 해준다.

 

 

[코드]

import sys
import heapq

N = int(sys.stdin.readline())
queue = []
for _ in range(N):
    S, T = map(int, sys.stdin.readline().split())
    queue.append([S, T])

queue.sort()
room = []
heapq.heappush(room, queue[0][1])
for i in range(1, N):
    if queue[i][0] < room[0]:
        heapq.heappush(room, queue[i][1])
    else:
        heapq.heappop(room)
        heapq.heappush(room, queue[i][1])

print(len(room))