[알고리즘] Greedy Algorithm - Interval Scheduling

Interver scheduling은 어떠한 일 j가 s_j에서 시작해서 f_j에서 끝난다고 했을 때, 다른 일들과의 수행 시간이 겹치지 않으면서 주어진 일들을 최대한 많이 할 수 있는 조합을 찾는 스케줄링 문제이다. 그렇기 때문에 두가지 일이 있다고 했을 때, 이 두가지 일은 절대 겹쳐서는 안되며 최대한 많은 일을 수행해야만 한다. 우리는 여기서 greedy algorithm을 이용해서 반례가 되는 경우들을 제외해서 최적의 조합을 찾을 것이다. 이 반례를 우리는 4가지 경우에 대해서 생각해 볼 수 있는데, 그 4가지 경우는 다음과 같다.

1. Earliest start time: 일찍 시작하는 일부터 선택해보자.
2. Earliest finish time: 일찍 끝나는 일부터 선택해보자.
3. Shortest interval: 수행 시간이 짧은 일부터 선택해보자.
4. Fewest conflicts: 적게 겹치는 일부터 선택해보자.

그러면 이제 하나씩 반례를 찾아보도록 하자.

Counter example of 1 >
이 경우 최적의 답은 첫번째 줄의 4가지 일을 선택하는 것이다. 하지만 1번의 조건으로 선택을 하면 두번째 줄의 1가지 일만 선택하고 끝나게 된다. 그렇기 때문에 일찍 시작하는 일부터 선택한다는 것은 최적의 해를 찾을 수가 없다.

Counter example of 3>
이 경우 최적의 답은 첫번째 줄의 2가지 일을 선택하는 것이다. 하지만 3번의 조건으로 선택을 하게 되면 두번째 줄의 1가지 일만 선택하고 끝나게 된다. 그렇기 때문에 수행 시간이 짧은 일부터 선택하게 되면 최적의 해를 찾을 수가 없다.

Counter example of 4>
이 경우 최적의 답은 첫번째 줄의 4가지 일을 선택하는 것이다. 하지만 4번의 조건으로 선택하게 되면 두번째 줄의 가운데 1가지 일만 선택하고 끝나게 된다. 최소한으로 겹치는 일을 선택해야 하기 때문이다. 다른 일은 기본적으로 4가지 일이 겹치게 되는데, 오직 두번째 줄의 가운데 1가지 일만 2가지 일만 겹치게 되어 선택하게 된다. 그렇기 때문에 적게 겹치는 일부터 선택하게 되더라도 최적의 해를 찾을 수가 없다.

마지막으로 2번의 경우에 대해서 반례를 찾으려고 해도 찾을 수가 없다. 그러면 일찍 끝나는 일부터 선택하는 것이 맞다는 이야기인데, 왜 그런지 증명해보자.
만약에 greedy algorithm으로 찾은 답이 최적의 해가 아니라고 가정해보자. 이때, greedy algorithm으로 해를 찾을 때 최적의 해와 r번째까지는 결과가 같다고 생각해보자. 최적의 해에서 r+1번째 해까지 greedy algorithm과 똑같이 만들 수 있고, 이 해가 여전히 최적의 해라면 greedy algorithm의 해와 r+1번째까지 같게 된다. 그러면 r번째까지 결과가 같다는 가정에 모순이 된다.