그리디알고리즘, Heap

Heap

push와 pop이 발생할 때마다 정렬이 되는 자료구조이다.

import heapq를 작성하여 이용할 수 있다.

생성은 리스트로 한 후에, value를 push, pop할 때만 heapq.heappush(list, value)와 heapq.heappop(list)를 사용하며, 예시는 다음과 같다.

import heapq
Heap = []

heapq.heappush(Heap, 5)
heapq.heappush(Heap, 2)
heapq.heappush(Heap, 4)
heapq.heappush(Heap, 1)
heapq.heappush(Heap, 8)
print(Heap)

# [1, 2, 4, 5, 8]

heapq.heappop(Heap)
heapq.heappop(Heap)
print(Heap)

# [4, 5, 8]

백준 11000 강의실 배정

문제

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

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

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

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

입력

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

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

출력

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

예제입력1

예제출력1

Idea

다음 강의가 시작될 때, 빈 강의실이 있으면 그 강의실에서 수업을 하고, 그렇지 않으면 새로운 강의실에서 수업을 한다.

다음 강의가 시작될 때만 event가 발생하기 때문에, 그 시각을 기준으로 비어있는 강의실을 알아야한다.
현재 진행중인 강의들의 종료 시각 vs 다음 강의 시작 시각

다음 강의가 먼저 시작한다면, 비어있는 강의실이 없다는 의미이므로 새로운 강의실에서 수업을 해야하고, 종료된 강의실이 있다면 그 곳에서 수업을 하면 된다.

현재 진행중인 모든 강의들의 종료 시각과 다음 강의 시작 시각을 모두 비교할 수도 있다. 하지만 하나의 강의실만 비어있으면 되기 때문에 가장 먼저 종료되는 강의가 다음 강의가 시작하기 전에 끝난다면 강의실이 재사용할 수 있다.
다음 강의가 시작할 때마다 가장 먼저 종료되는 강의의 종료 시각을 알아야하기 때문에 현재 진행중인 모든 강의의 종료 시각이 항상 정렬되는 자료구조를 사용하면 시간복잡도가 개선될 것이다.
현재 진행중인 모든 강의의 종료 시각을 Heap 자료구조를 이용하여 저장한다.

Implementation

모든 강의를 [시작시간, 종료시간]으로 Class list에 입력 후 시작시간 순서로 정렬한다.
가장 먼저 열리고 빨리 끝나는 수업의 종료시각을 heap에 push한다.
다음 수업의 시작시각과 기존에 진행중인 수업들 중 가장 빨리 끝나는 수업의 종료시각을 비교한다.

다음 수업의 시작시각이 더 늦는다면, 기존에 진행중인 수업들 중 가장 빨리 끝나는 수업의 종료시각이 끝나서 강의실이 비워지기 때문에 heap에서 pop할 수 있다.
그게 아니라면 아무 행동도 취하지 않는다.

3번과 관계 없이 새로 수업을 시작하게 되면 heap에 종료시각을 push한다.

3과 4를 보면 pop보다 push가 같거나 많을 수 밖에 없다.

만약 초반에 겹치는 강의가 많아서 강의실을 많이 사용하다가, 후반에 1개만 쓰게 되더라도 사용이 끝난 강의실은 그대로 비어있고 그 강의실에서 수업한 마지막 수업의 종료 시각이 heap에 남겨져있다.

그러므로, heap의 전체 개수를 출력하면 여태까지 동시에 최대로 사용한 강의실의 개수가 된다.

Code

import heapq
import sys

N = int(sys.stdin.readline())
Class = []
for _ in range(N):
    Class.append(list(map(int, sys.stdin.readline().split())))
Class.sort()

heap = []

heapq.heappush(heap, Class[0][1])
for index in range(1, N):
    if(Class[index][0]>=heap[0]):
        heapq.heappop(heap)
    heapq.heappush(heap, Class[index][1])
print(len(heap))

백준 11000번