개요
당신이 유명한 영화 배우여서 n 개의 작품 중에서 몇개를 골라서 출연해야 한다고 하자. 각 제안은 figure 1과 같이 기간을 명시하며, 우리는 빨강색으로 표시된 최적의 해(주어진 기간 동안 최대한 많은 작품에 출연하는 것)를 찾아야 한다. 이를 일반화 하면 아래와 같다.
입력: 어떤 선 위에 놓여 있는 n개의 구간(interval)들의 집합[1] 출력: 서로 겹치지 않는(disjoint, non-overlapping) 구간들의 가장 큰 부분집합[2]
이를 해결하기 위한 알고리즘들을 알아 보자.
알고리즘
Earliest Job First
해당 알고리즘은 가능한 한 가장 이른 시점에 시작하는 작업부터 순차적으로 선택하는 알고리즘이다. 이를 아래와 같은 수도 코드(psuedo code)로 표현할 수 있다.
While ([math]\displaystyle{ I \ne \emptyset }[/math]) do Accept the earliset starting job [math]\displaystyle{ j }[/math] from [math]\displaystyle{ I }[/math]. Delete [math]\displaystyle{ j }[/math], and intervals which intersect [math]\displaystyle{ j }[/math] from [math]\displaystyle{ I }[/math].
하지만 이는 figure 2와 같은 반례에서 알 수 있듯이, 정확하지 않은(not correct) 알고리즘이다.
Shortest Job First
해당 알고리즘은 가능한 한 가장 짧은 작업부터 순차적으로 선택하는 알고리즘이다. 이는 아래와 같은 수도 코드로 표현할 수 있다.
While ([math]\displaystyle{ I \ne \emptyset }[/math]) do Accept the shortest possible job [math]\displaystyle{ j }[/math] from [math]\displaystyle{ I }[/math]. Delete [math]\displaystyle{ j }[/math], and intervals which intersect [math]\displaystyle{ j }[/math] from [math]\displaystyle{ I }[/math].
하지만 이 역시, figure 3와 같은 반례가 있으므로, 정확하지 않은 알고리즘이다.
First Job to Complete
해당 알고리즘은 가장 빠르게 끝나는 작업부터 순차적으로 선택하는 알고리즘이다. 이는 아래와 같은 수도 코드로 표현할 수 있다.
While ([math]\displaystyle{ I \ne \emptyset }[/math]) do Accept job [math]\displaystyle{ j }[/math] with the earliest completion date from [math]\displaystyle{ I }[/math]. Delete [math]\displaystyle{ j }[/math], and intervals which intersect [math]\displaystyle{ j }[/math] from [math]\displaystyle{ I }[/math].
이때 해당 알고리즘은 최적의 해를 보장한다. 이는 아래와 같은 증명을 가진다.
어떠한 job x가 가장 먼저 끝나는 작업이라고 하자. 이때 x가 종료되기 전에 시작하는 다른 job들은 x보다 늦게 끝나므로, 반드시 x와 겹친다. 따라서 그들 중에서는 최대 1개만 고를 수 있다. 이때 해당 그룹에서 가장 먼저 끝나는 작업이 x이므로, x를 선택하는 것이 가장 많은 기회를 남긴다.