백준 11000 강의실 배정

문제 링크

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

알고리즘

자료구조
그리디
정렬
우선순위 큐

깃허브 블로그 시작하고 처음으로 오늘 푼 문제를 올려본다. 문제 번호가 깔끔해서 풀어봤다.

비슷한 문제

풀이

아이디어가 떠오르지 않는다면 쉽지 않은 문제인 것 같다. 문제 이해는 쉽지만 어떻게 풀지 난감해서 고민을 했다.

우선순위 큐를 이용해서 풀면 된다.

강의 시작 시간과 끝나는 시간이 담긴 리스트를 오름차순으로 정렬한 다음에 첫 번째 강의가 끝나는 시간을 힙에 넣는다.
두 번째 강의부터 차례대로
1. 만약 힙의 첫 번째 원소(현재 진행 중인 강의 중 가장 빨리 종료되는 회의 시간)가 다음 강의의 시작 시간보다 크다면(늦다면) 힙에 다음 강의 종료 시간을 넣어준다.
2. 반대로 힙의 첫 번째 원소가 다음 강의의 시작 시간보다 작다면 시간대가 겹치지 않아서 추가 강의실이 필요 없기 때문에 현재 힙의 원소를 방출하고 다음 회의 종료 시간을 넣어준다.
즉, 시간대가 겹칠 때마다 힙 내부의 원소 개수는 늘어나고, 시간대가 겹치지 않는다면 가장 빨리 끝날 예정인 강의 종료 시간을 제거하고 새로운 강의의 종료 시간을 넣는 것이다.
결과적으로 힙 내부 원소의 개수가 필요한 강의실의 개수다.

전체 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())

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

heap = []
heapq.heappush(heap, lst[0][1])

for i in range(1, n):
    if heap[0] > lst[i][0]:
        heapq.heappush(heap, lst[i][1])
        
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, lst[i][1])
        
print(len(heap))
        