0. 기본 정보

0-A. 개요

백준 - 11000번 문제에 대한 분석임.

0-B. 문제 정보

백준 - 11000번: 강의실 배정

---

1. 정답 코드

import sys
import heapq

input = sys.stdin.readline


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



answer = []
heapq.heappush(answer, l[0][1])

for i in range(1,n):
    if l[i][0] < answer[0]:
        heapq.heappush(answer, l[i][1])
    else:
        heapq.heappop(answer)
        heapq.heappush(answer, l[i][1])


print(len(answer))

---

2. 핵심 풀이

• 최소의 강의실을 사용하기 위해선 강의가 종료되는 시간에 맞춰 시작시간이 같거나 최대한 가까운 강의들을 연달아 넣어야 한다.
• 이때 효과적으로 각 강의실마다 강의가 종료되는 최소 시간과 새로운 강의의 시작 시간을 비교하기 위해 heapq 모듈을 사용한다.

2-A. 핵심 풀이

• 입력 받은 강의 시간 list를 강의 시작시간 기준으로 오름차순 정렬해준다.
• 강의 시간 list 내 1번째 요소의 강의 종료 시간을 heap-ordered list에 넣어준다.
• 이후 강의 시간 list의 2번째 요소부터 마지막 요소까지 강의 시작시간과 heap-ordered list의 최소값(강의가 가장 빨리 끝나는 시간)과 비교하여
  • 강의 시작시간이 같거나 더 클 경우 해당 요소의 강의 종료 시간을 heap-ordered list에 집어넣고 최소값은 삭제해준다.(기존 강의실을 사용하기 때문)
  • 강의 시작시간이 더 작을 경우 해당 요소의 강의 종료 시간을 heap-ordered list에 집어넣어준다. (새로운 강의실을 추가)
• 마지막 요소까지 비교를 진행 후 heap-ordered list의 남아있는 요소의 갯수를 출력한다.
  (요소의 갯수 = 강의실의 갯수)

---

ref

• https://hongcoding.tistory.com/79