백준 회의실 배정 : 가능한 space를 최대한 크게 만들자.

 그리디 알고리즘을 적용하는 문제 중에는, 백준 회의실 배정 문제가 있습니다. 오늘은 이 문제를 같이 풀어보도록 하겠습니다.

 

 

---

 그 전에, 이것 먼저 보여봅시다.

 

 이것을 보이는 것은 어렵지 않습니다. 구간 [a,b]에 [c,d]가 포함된다면, a<=c이고, d<=b입니다. 시간 [c,d]에 넣을 수 있는 최대 갯수를 B라고 특정 지어 봅시다.

 

 

 그러면 대충 이런 식으로 스케쥴을 할당할 수 있을 겁니다. 구간 [c,d]가 [a,b]를 포함한다면, a<=c이고, d<=b입니다. 그렇다면, 아래와 같은 그림을 그릴 수 있습니다.

 

 

 그러면, [a,b]는 [c,d]에 비해, slot(A)와 slot(B)를 가지고 있습니다. 그리고 구간 [c,d]도 포함하고 있고요. 그러면 일단, [c,d]에서의 최적의 스케쥴을 할당을 하면 벌써 B개입니다.

 

 

 [a,c]나 [d,b]에 들어갈 회의가 하나라도 있다면? 이 때는 B보다는 많이 할당할 수 있습니다. 물론, 이게 최적의 해인지 아닌지는 모르겠습니다. 하지만, 위와 같은 경우, B보다는 많이 할당할 수 있는 것은 자명해 보입니다. 따라서, 우리는 어떠한 시간에 회의실을 할당했을 때, 남은 시간 slot을 최대화 시켜야 한다는 것을 알 수 있습니다.

 

 이러한 류의 그리디는 생각보다 많이 보이므로, 알아두시면 도움이 많이 됩니다.

 

 

---

 이 관찰을 했다면, 어떤 게임을 생각해 봅시다. 그 게임의 규칙은 아래와 같습니다.

 

 그러면, 회의 2개가 있다고 생각해 봅시다. 하나는 [s1, e1], 또 다른 하나는 [s2, e2]. 이렇게 있다고 생각해 봅시다. 전자를 택한 후에, 할당 가능한 슬롯은 [e1, inf]가 되고, 후자를 선택한 후에는 [e2, inf]가 됩니다. 그리고 e1<e2라고 생각해 봅시다.

 

 

 전자를 선택했을 때입니다. 그리고 후자를 택했을 때에는 어떻게 될까요?

 

 

 선택할 수 있는 슬롯이 더 적어집니다. 따라서, 끝나는 시간이 빠른 것을 선택하는 게 이득입니다. 그 슬롯에 할당이 가능한 것들 중에서요. 만약에 끝나는 시간이 같으면 어떨까요? 이것도 고려를 해야 할까요?

 

 

 결론부터 말하면 네. 입니다. s(1)은 s'부터 e'까지 회의를 했다고 하고, s(2)는 e'부터 e'까지 회의를 했다고 생각해 봅시다. 그러면, 문제 조건에 의해서, s(1)을 한 다음에 s(2)를 할 수도 있을 겁니다. 한 회의가 끝나는 동시에 다른 회의가 시작될 수 있다고 했기 때문입니다. 그런데, s(2)를 먼저 선택했다고 가정해 봅시다.

 

 

 그러면, 가용 영역인 possible은 s(1)을 선택하지 않았는데도 [e', inf]로 줄어버립니다. 이 구간에 s(1) 구간인, [s', e']은 속하지 않습니다. 그런데, 끝나는 시간이 같다면, 시작 시간 순으로 정렬한 경우에는 이야기가 달라집니다. 이 때에는 끝나는 시간이 s(1)과 s(2)가 같다면, s(1)이 s(2)보다 앞에 오게 되는데요.

 

 

 그러면, s(1)을 선택하고 나면, [e', inf]가 가용 영역으로 들어옵니다. s(2)의 구간 [e', e']은 possible 영역에 속하므로, 선택 가능합니다. 따라서, 끝나는 시간 오름차순, 2차 기준은 시작 시간 오름차순으로 정렬해 주면 됩니다.

 

 

---

 이것을 코드로 봅시다.

 

 

 s가 회의 시작 시간, e가 회의가 끝나는 시간일 때, 1차 기준을 끝나는 시간이 빠른 순으로, 2차 기준을 시작 시간이 빠른 순으로 정렬하였습니다.

 

 

 18번째 줄부터 24번째 줄을 봅시다. 17번째 줄에서 end_time = -1로 설정해 놓았는데요. 처음 할당 가능한 슬롯이 [-1, inf]라는 의미입니다. loop를 돌 때 마다, 현재 가능한 Time 구간은 [end_time, inf]입니다. 그런데, [s', e'] 회의가 있는데요. 만약에 s'이 end_time보다 작으면 어떤가요? 그러면 [s', e']이 [end_time,inf]에 속하나요? 아닙니다. 따라서, 이 때에는 continue를 하면 됩니다.

 

 그렇지 않다면, end_time <= s이므로, 회의 시간이 가능한 Time 구간에 속합니다. 따라서, 선택을 해 주고, end_time을 업데이트 해 주면 됩니다.