백준 11000번 : 강의실 배정

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

11000번: 강의실 배정

 

다른 비슷한 문제와 헷갈려서 조금 해맸던 문제이다.

 

시작시간과 종료시간이 있는 N개의 강의가 입력으로 주어지고, 강의마다 강의실을 배정하려고 한다. 한 강의가 끝나자마자 다른 강의를 시작할 수 있지만, 강의 시간이 겹친다면 그 강의실은 현재 진행중인 강의가 끝날때까지 사용할 수 없다. 강의실을 최소한으로 사용했을때 강의실 개수를 구하는 문제다.

 

얼핏봤을때 회의실 배정 문제와 비슷해서 N개의 강의를 종료시간 기준으로 오름차순 정렬하고 풀었더니 오답이었다. 회의실 배정 문제는 주어진 강의를 하나의 강의실에 최대한 많이 배정해야하기 때문에 가장 빨리 끝나는 강의 순서대로 넣었다. 그런데 이 문제에서는 한 강의실에서 강의가 끝났을 때 남은 강의 중 가장 빨리 시작하는 강의를 배정해야 하기 때문에 시작시간을 기준으로 오름차순 정렬을 해야한다. 그래서 가장 빨리 끝나는 강의의 종료시간은 우선순위 큐를 활용하여 따로 계산한다.

 

시작시간이 빠른 강의부터 순서대로 탐색하면서 강의실을 배정한다. 매번 강의를 배정할때마다 그 강의의 종료시간을 우선순위 큐에 넣어주는데, 만약 배정하려는 강의의 시작시간이 현재 강의실이 배정된 강의 중 가장 빨리 끝나는 강의의 종료시간보다 같거나 늦다면 우선순위 큐를 팝 해주고 배정하려는 강의의 종료시간을 큐에 넣어준다.

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
s = sorted([tuple(map(int, input().split())) for _ in range(n)])
q = [s[0][1]]
for i in range(1, n):
    if s[i][0] >= q[0]:
        heapq.heappop(q)
    heapq.heappush(q, s[i][1])
print(len(q))