99클럽 코테 스터디 17일차 TIL Boj 19598. 최소 회의실 개수

Approach

• 그리디스러운 문제 유형과 시간을 정렬해야 한다는 것을 보고 우선순위 큐를 떠올렸다.
• 우선 시작 시간을 기준으로 정렬을 한 뒤, 배열을 순회하면서 힙에 종료 시간을 기준으로 우선순위 설정을 해주었다.
• 이렇게 한다면, 종료 시각이 긴 강의실은 끝까지 힙에 존재할 것이고, 앞에서부터 사용한 순서대로 교체될 것이기 때문에 최종적으로 힙의 길이만큼을 출력한다면 강의실의 개수가 된다.

---

Solution 💡

import sys
from heapq import heappop, heappush

N = int(sys.stdin.readline().strip())
lst = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
lst.sort(key=lambda x: x[0])
hq = []

for start, end in lst:
    if not hq:
        heappush(hq, (end, start))
    
    else:
        if hq[0][0] > end and hq[0][1] < start:
            heappush(hq, (end, start))
        
        elif hq[0][0] <= start:
            heappop(hq)
            heappush(hq, (end, start))
        
        elif hq[0][0] > start:
            heappush(hq, (end, start))

print(len(hq))