[백준(BOJ)] 11000번 강의실 배정 - 파이썬/python

문제

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

11000번: 강의실 배정

S에 시작해서 T에 끝나는 N개의 수업이 주어질 때, 모든 수업을 가능하게 하는 최소 강의실의 개수를 구하는 문제다.

예시

Example 1:

Input: 3
     1 3
     2 4
     3 5
Output: 2

풀이

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n = int(input())
lessons = [list(map(int, input().split())) for _ in range(n)]
lessons.sort()

heap = []
# 첫 번째 수업의 끝 시간을 힙에 추가
heappush(heap, lessons[0][1])

for i in range(1, n):
  # 현재 수업의 시작 시간이 힙의 가장 일찍 끝나는 수업의 끝 시간보다 크거나 같을 경우
    if lessons[i][0] >= heap[0]:
  # 가장 일찍 끝나는 수업 제거하고 현재 수업의 끝 시간으로 업데이트 (이전 강의실 재사용)
        heappop(heap)
    heappush(heap, lessons[i][1])

print(len(heap))

 

- 수업을 시작 시간을 기준으로 정렬하고, 최소 힙을 사용하여 힙에는 현재 진행 중인 수업 중 가장 일찍 끝나는 수업의 끝 시간을 넣어준다.

- 다음 수업부터 반복하면서 현재 수업의 시작 시간이 힙의 가장 일찍 끝나는 수업의 끝 시간보다 크거나 같으면 해당 수업의 끝 시간으로 힙을 업데이트하고, 그렇지 않다면 현재 수업의 끝 시간을 힙에 추가한다.

- 모든 수업에 대해 반복한 후, 힙의 길이가 최소 강의실의 개수가 된다.