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

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

11000번: 강의실 배정

 

문제 정의

수업들의 (시작하는 시간, 끝나는 시간) 을 확인하여, 필요한 강의실을 구하는 문제입니다.

 

풀이 방법

1. 수업 시간을 시작하는 시간을 기준으로 정렬을 합니다.
2. 첫 수업은 반드시 방이 필요하므로, 방에 수업을 추가합니다.
3. 이 때, 방에 들어간 수업의 시작 시간은 뒤에 수업들에게 필요하지 않고, 수업의 끝나는 시간이 필요합니다.
   그래서 수업시간의 끝나는 시간을 방에 대한 정보로 저장합니다.
4. 반복문으로  수업을 확인하면서 수업시간의 시작하는 시간보다, 방의 끝나는 시간보다 빠를 때는 방을 추가합니다.
5. 아니라면 방의 끝나는 시간을 해당 수업의 끝나는 시간으로 수정합니다.

이 때, 방은 min heap으로 되어있어서, 끝나는 시간은 가장 빠른 것이 나오게 됩니다.

import heapq

N = int(input())
classTime = [tuple(map(int,input().split())) for _ in range(N)] 
classTime.sort()

Room = []
# 끝나는 시간을 Room에 추가합니다.
heapq.heappush(Room, classTime[0][1])

for i in range(1,N):
    # 시작하는 시간이 끝나는 시간보다 빠를 경우
    if classTime[i][0] < Room[0]:
        # Room 추가
        heapq.heappush(Room, classTime[i][1])
    else:
        heapq.heappop(Room)
        heapq.heappush(Room,classTime[i][1])

print(len(Room))