[BOJ] 1374번 강의실 파이썬

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

풀이

#정렬 #그리디 #우선순위큐

1. 강의를 시작 순서로 정렬한다.

arr.sort(key = lambda x:x[1]) # 시작 시간으로 오름차순 정렬

2. 우선 순위 큐(heapq)를 이용하여 강의실 수를 계산한다.

arr에 저장되어 있는 순서대로(시작 순서가 이른 순서대로) 반복문을 돌면서 i 수업이 heap에 저장된 가장 일찍 끝나는 수업보다 늦게 시작하는 경우에는 수업시간이 겹치지 않는다는 것을 의미하기 때문에 heap에서 가장 일찍 끝나는 수업을 내보낸다. (내보낸 수업  → i 수업 이어서 같은 강의실에서 진행한다는 의미!)

3. i 수업의 끝나는 시간을 힙에 추가한다.

4. 힙의 길이 중 최대값이 필요한 최소 강의실 수가 된다.

 

😲 힙 사용법

파이썬의 heapq 라이브러리는 기본적으로 최소힙으로 구현된다.

heapq로 우선순위큐를 구현한다.(PriorityQueue와 다르게 Thread-Safe하지않지만 그렇기 때문에 더 빠르다  → 코테 문제 풀 때는 heapq 사용하자)

1. heappush - 값 추가

import heapq

heap = []

heapq.heappush(heap, 2)
heapq.heappush(heap, 1)

#[1,2]

2. heappop - 값 삭제

import heapq

heap = []

heapq.heappush(heap, 2)
heapq.heappush(heap, 1)

heapq.heappop(heap) #1이 pop됨

3. heapify - 힙으로 변환

import heapq

heap = [5, 3, 2, 1]

heapq.heapify(heap)

# [1, 2, 3, 5]

코드

import heapq

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

arr.sort(key = lambda x:x[1]) # 시작 시간으로 오름차순 정렬

min_heap = []
count = 0

#다른 수업 시간과 겹치지 않으면 이전 수업 pop
for i in arr:
    while min_heap and min_heap[0]<=i[1]: #가장 일찍 끝나는 수업보다 늦게 시작하면(겹치지 않으면)
        heapq.heappop(min_heap) #heap에서 가장 작은 원소 내보냄
    heapq.heappush(min_heap, i[2]) #i 수업의 끝나는 시간 힙에 추가
    count = max(count, len(min_heap))

print(count)