BOJ 11000번: 강의실 배정

www.acmicpc.net/problem/11000

11000번: 강의실 배정

아이디어:

처음에는 저번에 다른 회의실 문제를 풀었을 때처럼 종료시간을 기준으로 정렬하였다. 근데 그렇게 풀다보니 풀리지 않는 경우가 발생하였다.

4

1 3

2 4

4 8

3 9

이와 같은 경우에는 4 8 강의를 2 4 강의실에 배정해야 하는데 1 3 강의실에 배정이 되어서 오답이 나온다. 그래서 질문을 찾아보니.. 이 문제는 시작시간을 기준으로 정렬을 해서 풀어야 하는 문제였다. heapq를 사용하고, 끝나는 시간을 저장하는 배열end도 heapq를 사용하여 항상 최소힙으로 유지한다. 그러면 지금 보는 강의의 시작 시간이 만약 end의 top 즉 end[0]보다 작다면, 새로운 강의실이 필요한 것이므로 cnt++ 후 heappush를 이용하여 끝나는 시간을 새로 추가한다. 반대의 경우에는 하나를 pop한 후 heappush를 반복한다. 다만 이때는 새로운 강의실이 필요하지 않으므로 cnt는 그대로 둔다.

 

끝나는 시간을 기준으로 정렬했던 문제는 1931번 문제였는데, 이 문제는 지정된 회의실에서 최대한 많은 회의를 해야 했다. 하지만 이 문제는 지정된  회의실이 아니라 최대한 회의실을 적게 이용하는 것이므로, 시작시간이 중요한 것이다. 

 

import sys, heapq

N = int(sys.stdin.readline())
h = []
end = [] #회의 끝나는 시간 저장할 배열
cnt = 0
for _ in range(N):
    s, t = map(int, sys.stdin.readline().split())
    heapq.heappush(h, (s, t))

first = heapq.heappop(h) #첫번째 회의는 그냥 따로 처리했다.
end.append(first[1])
cnt+=1

for _ in range(N-1):
    now = heapq.heappop(h) #현재 회의

    if (now[0]<end[0]): #end의 top보다(제일 작은 시간보다) 시작시간이 큰 경우
        heapq.heappush(end, now[1])
        cnt+=1 #회의실 새로 필요
    else:
        heapq.heappop(end)
        heapq.heappush(end, now[1])

print(cnt)