Greedy 예제(4) Meeting Rooms

예제) 미팅 스케줄이 아래 그림과 같을 때, 최소 몇 개의 미팅룸을 잡아야 하는가?

 

 

 

 

 

미팅룸에 시작시간 순서대로 미팅이 할당된다.

 

현재 생성된 미팅룸 중에서 가장 빨리 끝나는 시간(END)보다 START 시간이 빠르면 미팅룸을 하나 더 생성한다. 

 

현재 가장 빨리 끝나는 시간을 기준으로 미팅룸을 만들지 안 만들지를 판단 ( Greedy 알고리즘 )

 

 

알고리즘 

 

1) 가장 빨리 끝나는 미팅룸 시간을 구하기 위해 최소 Heap을 생성한다.  

 

미팅1 ( 9 - 11 ) 할당

 

 

미팅2 ( 9 - 12 ) 할당

 

 

미팅2는 9시에 시작하므로 최소 Heap 11시보다 작다.

미팅룸을 하나 더 생성한다. 

 

 

미팅3 ( 10 -14 ) 할당

 

미팅3은 10시에 시작하므로 최소 Heap 11보다 작다. 

미팅룸을 하나 더 생성한다.

 

 

미팅4 ( 12 - 16 ) 할당

 

미팅4는 12시에 시작하므로 최소 heap 11보다 크다. 

최소 heap 11을 제거하고 Heap을 재정렬한다. 

미팅4가 끝나는 시간인 16시를 Heap에 추가한다.

 

 

이 과정을 반복하면 미팅룸은 최소 3개가 나온다. 

 

 

 

---

 

참고영상