11000. 강의실 배정 (Python)

11000번: 강의실 배정

 

풀이

 먼저 입력으로 받은 수업 시간들을 수업의 시작 시간을 기준으로 오름차순으로 정렬한다. 최소힙을 하나 만들어 첫 수업의 끝나는 시간을 넣어주고 강의실을 하나 사용한다.

 이제 for문을 통해 두 번째 수업부터 돌면서 현재 수업이 최소힙의 루트에 있는 종료 시간보다 빨리 시작하거나 빨리 끝난다면 해당 시간의 강의실은 사용할 수 없으므로 새로운 강의실을 배정한다. 만약 시작시간이 최소힙의 루트보다 크거나 같을 경우에는 해당 강의실에서 현재 수업을 할 수 있다는 것을 의미하므로 강의실을 새로 배정할 필요가 없다.

 

 이렇게 모든 수업들을 살펴보고 구한 최소 강의실의 개수를 출력해주면 된다.

 

코드

import heapq

if __name__ == '__main__':
    N = int(input()) # 수업의 개수
    lectures = [] # 수업들의 리스트

    for _ in range(N):
        S, T = map(int, input().split())
        lectures.append((S, T))
    lectures.sort() # 시작 시간을 기준으로 오름차순 정렬

    pq = [] # 수업들의 종료 시간을 담아주는 최소힙. 즉, 현재 사용되고 있는 강의실의 수업 종료 시간을 의미한다.
    heapq.heappush(pq, lectures[0][1]) # 먼저 첫 수업의 종료시간을 넣어주고
    res = 1 # 강의실을 하나 잡는다

    for i in range(1, N):
        s, t = lectures[i]
        nowEndTime = heapq.heappop(pq) # 강의실 중 가장 먼저 수업이 끝나는 강의실의 종료 시간을 꺼내온다.

        # 현재 수업의 시작 시간이나 종료 시간이 더 빠를 경우 
        # 현재 사용하고 있는 강의실에서는 수업이 불가능하여 새로운 강의실을 배정해야 한다.
        if t < nowEndTime or s < nowEndTime:
            heapq.heappush(pq, nowEndTime) # 꺼내온 종료 시간을 다시 넣어주고
            heapq.heappush(pq, t) # 새롭게 강의실을 사용해야 하므로 현재 수업의 종료 시간을 추가로 넣어준다.
            res += 1 # 강의실 하나 추가
        elif s >= nowEndTime: # 현재 수업의 시작시간이 종료 시간 이후일 경우 해당 강의실을 사용 가능하다
            heapq.heappush(pq, t) # 현재 수업의 종료 시간만 추가로 넣어준다.

    print(res)