[코테] 백준 그리디 1374번 문제

1374번 : 강의실

문제 링크

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

문제 설명

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

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

입력

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

출력

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

문제 풀이

1. 시작 시간이 적은 강의를 기준으로 정렬을 한다.
2. 배열을 선회하며 시작 시간이 가장 빠른 강의와 끝나는 시간이 가장 빠른 강의실을 비교해 강의장이 끝나고 다음 강의를 시작할 수 있으면 pop
3. 입력된 강의는 강의실에 push
4. 마지막으로 강의실의 개수를 세어 출력

from heapq import heappush, heappop

N = int(input())
arr = []
class_arr = []

for i in range(N) :
    class_num, start, end = map(int, input().split())
    heappush(arr, (start, end))
    
while arr : 
    start, end = heappop(arr)
    
    if class_arr and start >= class_arr[0] :
        heappop(class_arr)
        
    heappush(class_arr, end)
    
print(len(class_arr))