[알고리즘] Greedy Algorithm - Interval Partitioning

Interval partitioning은 n개의 강의에 대해서 같은 강의실에서 동시에 진행되지 않는 2개의 수업에 대해서 모든 수업을 시간과 강의실이 겹치지 않도록 최소한의 강의실을 배정하는 것을 목표로 한다. 수업 j에 대해서 시작은 s_j에 하고 끝은 f_j에 한다. 여기서 중요한 부분은 필요한 강의실의 수는 최소한 특정 시간에 강의의 개수보다 많거나 같아야 한다. 우선 알고리즘 code는 다음과 같다.

Interval partitioning에서 greedy algorithm으로 최적의 해를 찾을 수 있는 이유를 알아보려고 한다.
d는 greedy algorithm에서 배정한 강의실의 개수이다. 이때 d번째 강의실은 d-1번째 강의실에 배정이 된 강의와 시간이 겹치게 된 강의가 생겼을 경우에 할당되게 된다. 그렇게 되면 d번째 강의실은 s_j 이후가 될 것이고, 시작하는 시간 순서로 정렬했기 때문에 이렇게 강의가 겹치는 일은 s_j 이후에 시작되지 않는 강의에 의해서 발생이 된다. 그렇게 되면 s_j 이후 약간의 시간 후에는 강의가 d개가 겹치게 될 것이다. 이렇게 되면 필요한 강의실의 수가 최소한 특정 시간에 강의의 개수보다 많거나 같아지게 된다. 그래서 현재의 depth는 모르지만 새로운 강의실을 연다면 최소한 d개가 된다.