[백준 11000번] 강의실 배정 문제 풀이 (with Python)

 

< 문제 >

 

 

 

< 입출력 >

 

 

< 풀이 >

먼저 수업 시간을 입력한 후, 수업 시간 시작 시간으로 정렬을 해준다.

heapq를 이용하면 입력 순서에 상관없이 오름차순으로 정렬해주므로, heapq에 수업 종료 시간을 넣고 비교하는 방식으로 구현했다.

즉, heapq[0] 은 배정된 강의실 중 가장 빨리 끝나는 시간으로 다음 수업시간과 비교하여 더 빨리 끝나면, 해당 수업을 heapq에서 빼고 다음 수업시간의 끝나는 시간을 넣음으로서 하나의 강의실을 이어서 사용한다.

반대로, 다음 수업 시간보다 늦게 끝나는 경우, 새로운 강의실을 배정해야 하므로, 다음 수업 시간의 끝나는 시간을 heapq에 넣어준다.

 

 

 

< 구현 코드 >

import sys
import heapq

input = sys.stdin.readline
N = int(input())
Class = []

for i in range(N):
    Class.append(list(map(int, input().split())))

Class.sort()
result = []
heapq.heappush(result, Class[0][1])

for i in range(1, N):
    if Class[i][0] < result[0]:   # 끝나는 시간이 시작하는 시간보다 나중인 경우
        heapq.heappush(result, Class[i][1]) # 새 강의실 추가
    else:                          # 끝나는 시간이 시작하는 시간보다 이른 경우
        heapq.heappop(result)      # 그 전의 수업을 빼고
        heapq.heappush(result, Class[i][1])   # 다음 수업 추가 (같은 강의실 이어서)
    print(result)
print(len(result))