[백준/Python] 11000번 : 강의실 배정

시간 제한	메모리 제한	문제 티어
1 초	256 MB	골드 V

📜 문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 S_i에 시작해서 T_i에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, T_i ≤ S_j 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

📥입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 S_i, T_i가 주어진다. (0 ≤ S_i < T_i ≤ 10^9)

 

📤출력

강의실의 개수를 출력하라.

 

💡풀이

이 문제를 풀 때 포인트는 다음과 같다.

 

1) 가장 최소한의 강의실을 사용해서 모든 수업을 다 해야 한다.

2) 앞에 수업이 끝나는 시간이 뒤에 수업을 시작하는 시간과 같거나 작을 때 강의실을 추가할 필요가 없다.

3) 앞에 수업이 끝나는 시간이 뒤에 수업을 시작하는 시간보다 클 때 강의실을 추가해야 한다.

3) 수업이 끝나는 시간이 빠른 강의실부터 다음 강의를 이어서 해야한다.(그래야 강의실 최소화하면서 더 많은 강의를 할 수 있으므로!)

 

이에 따라 파이썬에서 제공해주는 heapq를 사용하여 min heap으로 풀었다. heapq 모듈은 binary tree 기반의 최소 힙(min heap) 자료구조를 제공한다. min heap을 사용하면 원소들이 항상 정렬된 상태로 추가/삭제되며, min heap에서 가장 작은값은 언제나 이진 트리의 루트(0)에 위치한다. 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가/삭제된다.

 

우선 데이터를 입력 받은 후 각 강의 시작 시간과 끝 시간을 묶어서 class_list List에 넣은 다음, class_list.sort(key = lambda x:x[0])를 통해서 시작 시간 기준으로 오름차순 정렬을 했다.

 

그러고 나서 시작 시간이 가장 빠른 수업의 끝 시간을 heappush 한 뒤, 다음 수업의 시작 시간과 같거나 작으면 pop 후 다음 수업의 끝 시간을 push하고, 만약 길다면 pop하지 않고 아예 다음 수업의 끝 시간을 push해서 강의실을 하나 더 만든다.

 

이 때는 우선순위 큐를 이용하는 것이므로 큐에 push를 해주어 큐가 오름차순으로 정렬 상태를 유지할 수 있도록 해준다.

 

import sys, heapq

input = sys.stdin.readline
N = int(input())

class_list = [None] * N
classroom = []

for i in range(N):
  S, T = map(int, input().rstrip().split())
  class_list[i] = [S, T]

class_list.sort(key = lambda x:x[0])
heapq.heappush(classroom, class_list[0][1])

for i in range(1, N):
  if class_list[i][0] < classroom[0]:
    heapq.heappush(classroom, class_list[i][1])
  else:
    heapq.heappop(classroom)
    heapq.heappush(classroom, class_list[i][1])

print(len(classroom))

 

형편없는 그림으로 그려본 heapq의 구조와 문제의 예제..

 

Reference

Heap queue : https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm