회의실 배정 문제 응용하기 -모든 수업을 가능하게 하는 회의실의 수는-

1. 문제

 

11000번: 강의실 배정 (acmicpc.net)

11000번: 강의실 배정

 

수업의 시작시간과 종료시간이 주어질때, 모든 수업을 가능하게 하는 최소의 회의실 수는..?

 

 

2. 풀이

 

회의실 배정 문제는 하나의 회의실로 최대한 많은 수업을 배치하는 문제로

 

종료시간이 빠른 순서대로 오름차순 정렬하고, "다음 수업 시작시간 >= 현재 종료시간"이면 하나의 회의실에서 가능하다는 알고리즘으로 해결했다

 

근데 이 문제는 모든 수업을 가능하게 하는 최소의 회의실 수를 구해야한다

 

어떻게 하냐면 시작시간이 빠른 순서대로 오름차순 정렬한다

 

먼저 가장 시작시간이 빠른 수업을 먼저 빼온다.

 

그 다음에, 여러 회의실을 사용할 수도 있다는 가능성을 생각해두고 리스트에 현재 수업에 대해

 

(종료시간, 시작시간)으로 정보를 넣어둔다

 

종료시간만 넣어도 되는거 아니냐고? 종료시간이 서로 같은데, 시작시간이 서로 다른 수업을 구분하기 위해서이다.

 

아무튼 그러면 먼저

 

[(t1,s1)]으로 첫번째 강의실이 사용되고 있다는 것을 표시할 수 있다

 

-----------------------------------------------------------------------------------------------------------------

다음에 시작시간이 빠른 s2,t2로 2번째 수업이 나올건데, 이 2번째 수업은 현재 사용중인 강의실 (t1,s1)에서 할 수 있을까?

 

그럴 조건이 뭘까?

 

2번째 수업의 시작시간 s2가 현재 수업중인 종료시간 t1이상이면 된다

 

그러면 2번째 수업은 현재 사용중인 (t1,s1)에 배치할 수 있다.. 이것을 어떻게 표시할 수 있을까?

 

2번째 수업의 종료시간 t2가 무조건 t1보다 크므로, 현재 첫번째 강의실에는 2번째 수업을 하고 있다고 표시해야한다.

 

그러니까 첫번째 수업은 이제 쳐내고 2번째 수업을 넣어야한다

 

[(t2,s2)] 이런 식으로 갱신해야, 3번째,4번째,5번째,...에 대해서도 이 강의실에 배치할지 결정할 수 있다

 

이렇게 갱신 안해놓으면.. 3번째,4번째,5번째가 첫번째 강의실에서 못하는데.. 시작시간은 점점 커지니까.. 첫번째 강의실에서 할 수 있다고 잘못생각할 수 있거든

-----------------------------------------------------------------------------------------------------------------

 

근데 만약에 2번째 수업의 시작시간 s2가 첫번째 수업의 종료시간 t1보다 작다면.. 2번째 수업은 첫번째 강의실에서 불가능하다.

 

왜냐하면 첫번째 수업이 끝나기전에.. 시작을 해야하니까 다른 강의실에서 수업을 해야한다는 것이다.

 

그것을 [(t1,s1),(t2,s2)]라고 표시해서, 현재 2개의 강의실을 사용중이다. 라고 표시를 하는 것이다

 

-----------------------------------------------------------------------------------------------------------

 

구체적으로

 

1) 우선순위 큐 1에 (시작시간, 종료시간)으로 모든 수업을 넣어줍니다

 

2) 우선순위 큐 1에서 시작시간이 가장 빠른 수업을 먼저 강의실을 표시하는 우선순위 큐 2에 (종료시간, 시작시간)으로 넣어준다

 

3) 이제 우선순위 큐1에서 수업을 하나씩 반복적으로 빼고, 현재 강의실을 표시하는 우선순위 큐2에 배치를 시작합니다.

 

강의실에서 현재 가장 빨리 종료하는 수업은 우선순위 큐2에서 먼저 나오는 (종료시간,시작시간)입니다.

 

최소의 강의실을 사용하려면, 당연히 가장 빨리 종료하는 강의실에 배치할 생각을 해야합니다.

 

3-1) 큐1에서 빼온 시작시간이 큐2에서 빼온 종료시간 이상이라면, 큐2에서 빼온 수업은 종료시키고, 큐1에서 빼온 새로운 수업을 이 강의실에 배치시킬 것입니다.

 

3-2) 큐1에서 빼온 시작시간이 큐2에서 빼온 종료시간보다 작다면, 큐1에서 빼온 수업은 다른 강의실에서 시작을 해야합니다.

 

그러므로 큐2에서 빼온 수업은 아직 종료되지 않았으니, 큐2에 (큐2에서 빼온 수업과 큐1에서 빼온 수업) 둘다 넣어줍니다.

 

import heapq
from sys import stdin

n = int(stdin.readline())

##모든 수업을 (시작시간, 종료시간)으로 우선순위 큐를 만들어준다
q = []

for _ in range(n):
    
    s,t = map(int,stdin.readline().split())

    heapq.heappush(q,(s,t))

##먼저 시작시간이 가장 빠른 수업을 강의실 우선순위 큐에 배치한다
s,t = heapq.heappop(q)

cnt_q = []

heapq.heappush(cnt_q,(t,s))

##수업을 강의실에 배치하기 시작
while q:
    
    ##배치해야할 새로운 수업
    s,t = heapq.heappop(q)
    
    ##현재 강의실에서 가장 빨리 종료하는 수업
    b_t,b_s = heapq.heappop(cnt_q)
    
    ##새로운 수업의 시작시간이, 가장 빨리 종료하는 수업의 종료시간 이상이라면?
    if s >= b_t:
        
        #그 수업은 종료시키고, 그 강의실에 새로운 수업을 배치합니다.
        heapq.heappush(cnt_q,(t,s))
    
    ##새로운 수업의 시작시간이 가장 빨리 종료하는 수업의 종료시간보다 작다면?
    else:
        
        ##아직 수업이 종료된 것이 아니니, 수업은 계속하고
        heapq.heappush(cnt_q,(b_t,b_s))
        
        ##새로운 수업은 다른 강의실에 배치해야합니다.
        heapq.heappush(cnt_q,(t,s))

##모든 수업을 배치하고나서, 표시된 강의실의 수가 최소의 강의실 수입니다.
print(len(cnt_q))

 

 

3. 되돌아보기..

 

회의실 배정 그리디 문제를 응용하는 문제긴 하지만..

 

종료시간으로 정렬하면 왜 안됐을까?

 

그거는 종료시간이 빠른데, 시작시간은 더 느린경우가 존재할 수 있어서 그렇다

 

6
1 3
2 5
3 4
4 12
8 10
4 11

 

이런 경우 시작 시간으로 정렬해서

 

1 3

2 5

3 4

4 11

4 12

8 10으로.. 

 

(1,3), (3,4) (4,11)

 

(2,5), (8,10)

 

(4,12)으로 3개잖아

 

종료시간으로 정렬하면, 

 

1 3

3 4

2 5

8 10

4 11

4 12인데..

 

(1,3), (3,4),(8,10)

 

(2,5)

 

(4,11)

 

(4,12)로 4개를 쓴다

 

----------------------------------------------------------------------------------------

 

우선순위 큐 하나만 쓰는게 아니고 2개를 써서.. "강의실에 수업중이다"라는 시뮬레이션 느낌을 주게 만들어서, 그 강의실에 수업중인 시간을 계속 갱신하는게

 

정말 미친 트릭이다

 

큐에 종료시간만 넣을수도 있겠지만.. (종료시간, 시작시간)을 넣어서.. 시작시간이 서로 다르지만 종료시간이 같은 수업을 구분해주는 디테일도 중요하겠다