[BOJ 11000, Python 3] 강의실 배정

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

11000번: 강의실 배정

 

풀이

강의실이 끝나는 시간을 우선순위 큐에 저장하여 새로운 수업이 들어오기 전에 while문이나 if문으로 해당 수업 시작 시간 이전에 끝날 수 있는 강의실을 비우게 하면 됩니다.

 

while문은 해당 수업 시작 전에 끝나는 모든 강의실을 비워두니까 쉽게 이해할 수 있습니다.

if문을 사용하는 것은 만약 현재 사용하는 강의실 수가 x개일 때, 강의실을 비울 수 있으면 강의실은 x-1개가 되고 현재 수업이 강의실을 사용해서 x개가 유지가 됩니다. 혹은 비울 수 있는 강의실이 없으면 현재 수업 x+1개가 최댓값이 됩니다. 그래서 if문은 항상 최댓값으로 유지할 수 있게 되어 for문을 끝내고 사용중인 강의실 수를 출력하면 됩니다.

 

코드

1. while문 사용

from heapq import *
input = __import__('sys').stdin.readline
n = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(n)])
hq = []
ans = 0
for i in range(n):
    while hq and hq[0] <= arr[i][0]:
        heappop(hq)
    heappush(hq, arr[i][1])
    ans = max(ans, len(hq))
print(ans)

 

2. if문 사용

from heapq import *
input = __import__('sys').stdin.readline
n = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(n)])
hq = []
for i in range(n):
    if hq and hq[0] <= arr[i][0]: heappop(hq)
    heappush(hq, arr[i][1])
print(len(hq))