📚 11000 - 강의실 배정

강의실 배정

이해

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

ex)

5
1 2
2 17
3 8
9 27
18 20

와 같이 있을 때

1 -> 2 -> 18
3 -> 9

답으로 2이다.

시간 제한이 1초이기 때문에, 2차 반복문을 사용할 시 시간 초과가 발생한다. (1 ≤ N ≤ 200,000)
이와 같은 문제를 풀 때는 우선순위 큐를 사용하면 된다.

5
1 2 heap 2저장
2 17 heap 2와 같으므로 업데이트 17
3 8 heap 17보다 8이 작으므로 heap에 8추가
9 27 heap 제일 작은 값 8보다 9가 크므로 heap 8제거 후, 27 추가 
18 20 heap 17 27 이므로, heap 제일 작은 값 17보다 크므로 17제거 후, 20추가

이와 같이

• 이전 도착시간 보다 현재 시작시간이 크거나 같다면 heap 업데이트
• 이전 도착시간 보다 현재 시작시간이 작다면 heap에 추가

규칙을 이용하면 된다.

소스

import sys  
import heapq  
  
read = sys.stdin.readline  
  
n = int(read())  
  
lesson = []  
  
for i in range(n):  
    s, t = map(int, read().split())  
    lesson.append((s, t))  
  
  
lesson.sort()  
  
room = []  
  
heapq.heappush(room, lesson[0][1])  
  
for i in range(1, n):  
    if room[0] > lesson[i][0]:  
        heapq.heappush(room, lesson[i][1])  
    else:  
        heapq.heappop(room)  
        heapq.heappush(room, lesson[i][1])  
  
print(len(room))