[백준] 11000번 강의실 배정

문제

강의별로 시작시간, 종료시간이 주어질 때 최소한의 강의실을 이용해 강의를 전부 진행할 때 그 때의 강의실 수를 구해라.

ex)

n = 3
start end
1	  3
2	  4
3	  5

풀이

최소한의 강의실을 사용하는 방법은 단순하다. 강의가 끝나자마자 시작가능한 강의를 해당 강의실에서 진행하면 된다.

자세한건 코드를 통해 살펴보자.

전체코드

import sys
import heapq
input = sys.stdin.readline

# 모든 수업을 해야하니 일단은 시작시간 오름차순
# 강의실 비면 들어가고 없으면 늘리면 됨
n = int(input())
lectureList = sorted([tuple(map(int, input().split())) for _ in range(n)], key = lambda x : x[0])
lectureRoomList = []
answer = 0

# 1개의 강의실은 무조건 존재하기에 첫 강의는 넣고 시작
# 끝나는 시간을 기준으로 힙을 만든다.
heapq.heappush(lectureRoomList, lectureList[0][1])
for startTime, endTime in lectureList[1:]:
	# 끝난 강의가 있으면 현재 강의와 교대
    if lectureRoomList[0] <= startTime:
        heapq.heappop(lectureRoomList)
	
    # 사용가능한 강의실이 없다면 확장
    heapq.heappush(lectureRoomList, endTime)
    # 힙의 최대길이가 최소 강의실 수
    answer = max(answer, len(lectureRoomList))

print(answer)