모그 스케줄링

일정을 시작 시각순으로 처리하자. 현재 선택되어 진행 중인 일정들의 수를 $c$라고 하자.

$c<N$이면 방 안에 사람이 있으므로 새 일정으로 인해 문제가 발생하지 않는다. $c=N$이 되는 순간에는 모두 방 밖에 있다. 이때 진행 중인 일정 중 가장 먼저 끝나는 일정을 $x$라고 하자. 첫 번째로 돌아오는 $x$의 주인이 문을 열려면 $x$의 출발 때 열쇠를 가지고 나갔어야 한다.

방이 완전히 비는 각 구간마다 이처럼 열쇠를 가져야 하는 일정이 하나씩 결정된다. 그 일정들은 시간상 서로 겹쳐서는 안 된다. 반대로 서로 겹치지 않는다면 열쇠를 해당 주인에게 차례대로 맡길 수 있으므로 모두 기다리지 않고 돌아올 수 있다.

따라서 앞서 결정된 열쇠 담당 일정의 귀환 시각을 $q$라고 할 때, 새로 방이 완전히 비는 상황에서 $l_x<q$이면 충돌이 발생한다. 이런 경우 현재 진행 중인 일정 하나를 선택에서 제외해야 한다.

이때 종료 시각이 가장 늦은 진행 중인 일정을 제외하는 것이 최적이다. 같은 시점에 진행 중인 일정 중 하나를 포기해야 한다면, 더 늦게 끝나는 일정을 제외하는 쪽이 이후에 방 안에 사람이 존재하는 시간을 더 늘린다. 이 교환 논증을 시작 시각순으로 반복 적용하면 선택한 일정 수가 최대가 된다. 충돌이 없으면 $q\leftarrow r_x$로 갱신한다.

종료 시각 기준 최소 힙과 최대 힙을 각각 유지한다. 이미 끝났거나 제거된 일정은 지연 삭제한다. 각 일정은 힙에 한 번씩 들어가고 나가므로 시간 복잡도는 $O(M\log M)$, 공간 복잡도는 $O(M)$이다.