그리디) BOJ G4 11000 강의실 배정

문제 정리

Git: https://github.com/Tarte12/CodingTest_KUT/commit/e52238192d7938363f1b5ff6e04e2e6b9c8211a7

최종 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
times = [tuple(map(int, input().split())) for _ in range(n)]
#times = [(s1, t1), (s2, t2), (s3, t3)...]
answer = 0
times.sort()
heap = [] #진행 중 강의들의 종료 시간

for s, e in times: #times는 배정되어야 하므로 다 돌아야 해
    while heap and heap[0] <= s:
        heapq.heappop(heap)
    heapq.heappush(heap, e)
    answer = max(answer, len(heap))
print(answer)

문제 리뷰

1) 왜 그리디일까?

• 문제 목표: 동시에 필요한 최소 강의실 수 = 어떤 시각에도 겹쳐서 진행 중인 강의의 최대 개수
• 새 강의가 시작할 때 가장 빨리 끝나는 강의실(종료 시간 최소) 우선 재사용
• 매 시점에 가장 빨리 끝나는 방 선택 => 이게 최소 방 갯수이므로 그리디

2) 핵심 아이디어를 어떻게 떠올릴까?

• 질문이 최대 몇 개 고를까? -> 끝나는 시간 오름차순 그리디
• 질문이 최소 자원(방/서버) 몇 개 필요? -> 동시 점유(= 최대 중첩) -> 스위핑/힙
• 설계 절차:
  1. 간격들을 시작 시간 오름차순 정렬
  2. "현재 진행 중" 집합을 종료 시간 min-heap으로 표현
  3. 새 간격(s, e) 처리 시 -> heap[0] <= s 것들을 모두 pop (방 재사용 가능)
  4. 현재 종료 시간 e를 push
  5. 숫회 중 len(heap)이 최댓값
• 핵심 불변식":
  - 힙에는 항상 끝나지 않은 강의의 종료 시각만 존재
  • 진행 중 강의 1개 = 방 1개 점유 => len(heap) = 현재 필요한 방 수

3) 회의실 배정이랑 뭐가 다른가?

문제	질문	전략	자료구조
회의실 배정(1931)	한 방에 겹치지 않게 최대 몇 개 회의를 고를까?	끝나는 시간 오름차순 그리디 선택	불필요
강의실 배정(11000)	최소 몇 개 방이 있어야 전부 배정 가능한가?	시작 시간 오름차순 + 종료시각 min-heap	필수 (heap)

4) 힙(Heap)과 heapq

• 파이썬 heapq는 min-heap만 제공 → 가장 작은 값이 루트 heap[0]
• 우선순위 큐로 쓰려면 “우선순위 = 수치”로 보고 그 수치(여기서는 종료시각)를 넣으면 됨
• 최대힙이 필요하면 값에 부호 반전(예: -x) 또는 (우선순위, 데이터) 튜플에서 우선순위를 음수로
  왜 heap[0]만 보고 “끝난 것들을 전부” 뺄 수 있나?
• min-heap에서 가장 작은 값이 루트
• heap[0] <= s이면 가장 빨리 끝난 것조차 s 이전/동시에 끝난 것이므로 pop
• pop 후 새 루트도 “그다음으로 작은 값” → 조건 만족 시 다시 pop
• while로 반복하면 s 시각 기준으로 끝난 것들을 전부 제거