문제
N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.
물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.
출력
첫째 줄에 필요한 최소 강의실 개수를 출력한다.
내 풀이
import sys
import heapq
input = sys.stdin.readline
n = int(input())
lectures = []
for i in range(n):
no, start, end = map(int, input().split())
lectures.append([start, end])
lectures.sort(key=lambda x:x[0])
rooms = []
heapq.heappush(rooms, lectures[0][1]) # 가장 이르게 시작하는 강의의 끝나는 시간을 넣음
for i in range(1, n):
if lectures[i][0] < rooms[0]: # 그 다음 강의 시작 시간이 첫 강의의 끝나는 시간보다 이르다면 (-> 새 강의실 필요)
heapq.heappush(rooms, lectures[i][1]) # heap에 그 강의의 끝나는 시간을 넣어주자.
else: # 그 다음 강의의 시작 시간이 이전 강의의 끝나는 시간보다 크다면 (-> 새 강의실 없이 이어서 강의)
heapq.heappop(rooms) # room을 비우자
heapq.heappush(rooms, lectures[i][1]) # 그리고 그 다음 강의의 끝나는 시간을 넣어주자.
print(len(rooms))코멘트
heap이라는 자료 구조를 이용하면 간단히 풀 수 있는 문제이다. heap은 트리 구조인데 부모-자식 노드가 작은 값 → 큰 값으로 정렬 (min heap), 큰 값 → 작은 값으로 정렬 (max heap)되는 트리 구조이다.
이를 이용해서 이전 강의의 끝나는 시간과 그 다음 강의의 시작 시간을 비교해줌으로써 heap에 넣고 빼는 식으로 구현하면 필요한 최소 강의실의 갯수를 구할 수 있다.
References
https://www.acmicpc.net/problem/1374
https://hyojeong94.tistory.com/133
https://littlefoxdiary.tistory.com/3
