[백준] 1374. 강의실 풀이 (Python)

1374번: 강의실

 

접근한 방법

그리디를 이용해 최소 개수로 최대한 많은 강의(작업)를 실행하기 위한 작업 스케줄링 문제입니다. 기본 아이디어는 강의들을 시작 시간을 기준으로 오름차순 정렬한 후, 그리디하게 선택하는 것입니다. 

 

1. 강의들을 시작 시간을 기준으로 정렬합니다.

2. 힙(우선순위 큐)을 사용하여 강의 시간을 스케줄링합니다. 힙은 강의의 종료 시간을 저장하는데 사용되고 항상 종료 시간을 기준으로 최소 힙(가장 작은 종료 시간을 루트에 두는 힙)으로 유지해야 합니다.

3. 정렬된 강의 리스트를 순회하면서 현재 강의의 시작 시간(s)과 힙의 가장 작은 종료 시간을 비교합니다. 만약 힙의 가장 작은 종료 시간이 현재 강의의 시작 시간 이전이라면, 이 강의를 선택하고 힙에 추가합니다. 그렇지 않은 경우, 이 강의는 현재 시점에서 선택할 수 없으므로 다음 순회로 넘어갑니다. 선택한 강의는 힙에 추가되고, 종료 시간을 업데이트합니다. 

4. 마지막으로 힙에 남아 있는 강의의 개수를 출력합니다. 이 값이 동시에 사용하고 있는 강의실의 최대 개수가 됩니다.

 

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
    _, s, e = map(int, input().split())
    arr.append((s, e))

from heapq import heappop, heappush
h = []
for (s, e) in sorted(arr, key=lambda x: x[0]):
    if h and h[0] <= s:
        heappop(h)
    heappush(h, e)
print(len(h))