[백준 11000] 강의실 배정 (with Python / 그리디 + 우선순위큐)

문제링크

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

11000번: 강의실 배정

문제설명

 

문제

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

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

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

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

입력

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

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

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

예제 입력 1 복사

3
1 3
2 4
3 5

예제 출력 1 복사

2

문제풀이

전에 풀었던 '회의실 배정' 문제와 비슷하다고 생각했다.

 

우선순위 큐(큐의 형태를 하고 있지만, 항상 정렬이 된 자료구조)를 사용했다.

우선순위 큐를 구현하기 위해 파이썬의 heapq 라이브러리를 활용하였는데

heapq는 기본구조가 최소힙이므로 첫번째 노드로 항상 가장 작은 요소가 된다.

 

	배열	힙 ( 완전이진트리 사용)
삽입	O(1)	O(logN)
삭제	O(N)	O(logN)

 

핵심

우선 순위 큐로 수행시간을 줄이는 방법을 생각할 수 있느냐가 핵심인 듯하다.

 

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
arr = [[0, 0] for _ in range(N)]
answer = 0 # 강의실 수
heap = []

for i in range(N):
    arr[i][0], arr[i][1] = map(int, input().split())

arr.sort(key=lambda x: x[0])
heapq.heappush(heap, arr[0][1]) # 첫 강의 끝나는 시간
for i in range(1, N):
    # heap[0] 가장 빨리끝나는 강의실임.
    # 다음 강의 시작시간이 더 작으면, 강의실 늘려야하므로
    if heap[0] > arr[i][0]:
        heapq.heappush(heap, arr[i][1])
    # 아니라면, 같은 강의실에서 가능
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, arr[i][1])

print(len(heap))