[알고리즘] 그리디 (2) - Interval scheduling

 

 

 

 

 

🧐 Interval Scheduling

n개의 작업이 존재하고, 해당 작업들을 수행하는 시간이 각각 [시작 시간, 완료 시간] 으로 주어져 있다고 하겠습니다.

 

같은 시간에는 하나의 작업만이 가능한 경우, 주어진 시간 내에 최대한 많은 작업들을 수행할 수 있도록 scheduling 하는 것을 Interval Scheduling 이라고 합니다.

 

이때 작업 $i, j$ 를 동시에 하지 못할 경우, $i$ 와 $j$ 는 overlap 되어 있다고 합니다.

 

 

 

 

 

 

⭐️ Psudocode

Initially R is the set of all jobs

A is empty    // A will store all the jobs that will be scheduled 

while R is not empty
        choose job $i \in R$
        add $i$ to $A$
        remove from $R$ all jobs that overlap with $i$

 

 

 

저희는 위 Psudocode에서 job i를 greedy 하게 골라 최적해를 구하는 방법을 알아내야 합니다.

 

 

 

 

 

 

 

총 4가지의 방법을 살펴볼 것이며, 각각의 알고리즘에 대하여 알고리즘이 고르는 작업과 최적해를 다음과 같은 색으로 나타내도록 하겠습니다.

Algorithm이 고르는 작업 : 회색
최적해 : 주황색

 

 

 

 

 

 

 

 

 

⭐️ Algorithm 1 - 시작 시간이 제일 빠른 작업 선택

위와 같이 시작 시간은 빠르지만 진행 시간이 매우 긴 경우 최적해를 구하지 못합니다.

 

 

 

 

 

 

 

 

⭐️ Algorithm 2 - 소모 시간이 제일 적은 작업 선택

위와 같이 소모 시간이 짧다고 하더라도 overlap 되는 작업이 많다면 최적해를 구하지 못합니다.

 

 

 

 

 

 

 

 

 

⭐️ Algorithm 3 - 해당 작업과 overlap 되는 작업의 개수가 제일 적은 작업 선택

overap 되는 것이 가장 적다고 하더라도 최적해를 구하지 못할 수 있습니다.

 

 

 

 

 

지금까지 살펴본 알고리즘들은 모두 최적해를 구하지 못하였습니다.

 

다음에 나오는 알고리즘을 통해 최적해를 구할 수 있습니다.

 

 

 

 

 

 

 

 

⭐️ Algorithm  4 - 끝나는 시간이 제일 빠른 작업부터 고르기

 

 

해당 알고리즘이 최적해를 반환하는 것에 대한 증명은 다음과 같이 이루어집니다.

 

앞선 알고리즘이 작업을 선택할 때마다 해당 작업과 overlap한 job들은 R 에서 모두 제거하므로, 당연히 algorithm4 에서 고른 job들은 서로 overalp하지 않습니다.

이제 두 집합 A와 O를 다음과 같이 정의하겠습니다.

A: Algorithm 4가 고른 작업들의 집합.
O : 최적해를 이루는 작업들의 집합.

두 알고리즘의 결과로 수행되는 작업의 개수가 같음을 증명하여야 최적해를 반환함이 증명됩니다.
$|A| = |O|$
claim 증명 시 위 theorem이 바로 증명됩니다.

$A = \left\{i_1, i_2, ..., i_k\right\}$ ,  $O = \left\{j_1, j_2, ..., j_m\right\}$ 이라 두고,
$s(i)$ 와 $f(i)$ 를 각각 job $i$ 의 시작 시간과 완료 시간이라고 하겠습니다.

그럼 k = m 을 증명하면 위 claim을 증명할 수 있습니다.

우선 귀납법을 이용하여 모든 $1 \leq r \leq k $ 에 대하여, $f($ $i_r$ $)$ $\leq$ $f($ $j_r$ $)$ 이라는 것을 증명해 보도록 하겠습니다.

r = 1 인 경우, Algorithm은 가장 빨리 끝나는 작업을 선택하기 때문에 $f($ $i_1$ $)$ $\leq$ $f($ $j_1$ $)$ 입니다.


r = k 일 때 성립한다도고 가정하도록 하겠습니다.

이때 $f($ $j_k$ $)$ 보다 시작 시간이 같거나 늦은 새로운 작업이 추가되었을 때, 최적해는 해당 작업을 포함할 것입니다.
이때 가정에 의하여 $f($ $i_r$ $)$ $\leq$ $f($  $j_r$ $)$ 이므로, Algorithm 역시 해당 작업을 추가할 수 있습니다.
따라서 $f($ $i_{k + 1}$ $)$ $=$ $f($ $j_{k+1}$ $)$ 이므로 모든 경우에 대하여 $f($ $i_r$ $)$  $\leq$  $f($ $j_r$ $)$ 입니다.

A의 개수 k과 O의 개수 m에 대하여,
m > k 인 경우, 바로 위에서 증명한 성질에 의하여 $f($ $i_k$ $)$ $\leq$ $f($ $j_k$ $)$ 가 됩니다.
따라서 $f($ $i_k$ $)$  < $s($ $j_{k+1}$ $)$ 이 되므로, 
algorithm은 $j_{k+1}$ 을 추가로 선택할 수 있습니다.

따라서 m > k 인 경우 algorithm에 모순이 되므로 $m = k$ 입니다.

 

 

 

 

해당 알고리즘에 대한 Psudocode는 다음과 같습니다.

 

 

 

⭐️ Psudocode

Initially R is the set of all jobs

A is empty    // A will store all the jobs that will be scheduled 

while R is not empty
        choose $i \in R$ such that finishing time of $i$ is least
        if $i$ does not overlap with requests in A
                add $i$ to $A$
        remove from $R$ all jobs that overlap with $i$
return the set $A$

 

 

해당 알고리즘의 시간 복잡도는 다음과 같습니다.

 

- 모든 작업들을 완료 시간 순서대로 정렬 : $O(n log n)$
- 현재 R 에서 끝나는 시간이 제일 이른 작업 고르기 : $O(1)$
- Overlap 검사 (작업 하나당): 마지막으로 고른 job이 끝나는 시간을 유지하여 현재 고려중인 job의 시작 시간과 비교해서 판별 가능합니다. $O(1)$

 

한번 검사한 작업은 다시 검사하지 않으므로 총 수행 시간은 다음과 같습니다.

$$O(n \; log \;n + n) = O(n\;log\;n)$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 모든 강의에 대한 강의실 배정

n개의 강의에 대하여, 각각의 강의는 시작 시간과 종료 시간이 주어진다고 하겠습니다.

 

같은 시간에 같은 강의실에서 최대 하나의 강의만 진행할 수 있다고 할 때, n 개의 강의를 하기 위해 최소로 필요한 교실 개수를 구해보도록 하겠습니다.

 

 

예시는 다음과 같습니다.

 

 

 

 

 

 

 

 

 

⭐️ Algorithm

현재 교실 배정이 안된 수업들 중에서 시작 시간이 제일 빠른 수업을 고른 뒤, 해당 수업을 가능한 교실에 배치합니다.

이때 가능한 교실이 없는 경우 새로운 교실에 배치합니다.

 

강의들의 집합 R에 대하여, $R$ 의 depth를 다음과 같이 정의하도록 하겠습니다.

R에 속한 강의들 중 어느 동일한 시점에서 수행되는 강의들의 최대 개수

 

 

depth 예시

 

 

이때 강의들의 집합 R에 있는 강의를 하기 위해서는 적어도 R의 depth 만큼의 교실이 필요합니다.

 

 

 

 

 

 

이를 통해 배정해야 할 강의실의 최소 수를 구하는 알고리즘은 다음과 같습니다.

 

 

 

 

⭐️ Psedocode

Initially R is the set of all requests

d = 0  // number of classrooms

Sort all the lectures in R based on their starting time

while R is not empty
           choose $i \in R$ such that start time of $i$ is earliest
           if $i$ can be scheduled in some classroom $k \leq d$
                     scheedule lecture i in classroom k
           else
                     allocate a new classroom $d + 1$ and schedule lecture $i$ in $d + 1$
                     d =d + 1

 

 

 

해당 알고리즘이 최적해를 반환하는 것에 대한 증명은 다음과 같습니다.

앞선 greedy algorithm이 depth 개보다 교실을 더 많이 요구한다고 가정하도록 하겠습니다.

depth의 값을 d라고 칭하도록 하겠습니다.

$j$ 가 $d + 1$ 번째의 교실을 요구하는 강의들 중 알고리즘이 처음으로 선택한 강의라 하겠습니다.

해당 알고리즘은 강의를 시간 순서대로 선택하므로, j와 겹치면서 시작 시간이 j 보다 이른 강의가 적어도 d개 있습니다.

따라서 j가 시작할 시점에서 R의 depth는 적어도 d + 1이 되고, 이는 R의 depth가 d라는 가정에 모순이 됩니다.

 

이제 해당 알고리즘의 시간 복잡도를 분석해 보면 다음과 같습니다.

 

 

 

- 모든 강의들을 시작 시간 순서대로 정렬 : $O(n \; log \;n)$
- 현재 R에서 시작 시간이 제일 이른 강의 고르기 : $O(1)$
- 교실 배치 : 각 교실별로 마지막으로 강의가 끝나는 시간을 유지하는 방법으로 현재 만들어진 교실이 d개인 경우 강의 하나당 O(d)의 시간이 소요됩니다.

 

한번 검사한 강의는 다시 검사하지 않으므로 총 수행 시간은 다음과 같습니다.

$$O(n \; log \; n + nd) = O(n^2)$$

 

 

 

 

 

 

 

 

 

 

🧐 시간 복잡도 향상시키기

priority queue를 이용하여 시간 복잡도를 향상시킬 수 있습니다.

이때 우선순위는 해당 교실에서 마지막 강의가 끝나는 시간으로 설정합니다.

새로운 강의는 마지막 강의가 끝나는 시간이 제일 빠른 교실에 배칠할 수 없는 경우 새로운 교실에 배정해야 합니다.

 

 

현재 강의를 기준으로 기존 교실에 배정할 수 있는지 체크하는 것은 priority queue의 findmin 연산을 사용하여 수행할 수 있습니다.

새로운 교실을 배정하는 것은 insert 연산을 사용합니다. $O(log \; n)$

현재 강의를 기존 교실에 배치하는 것은 기존 교실에서 마지막 강의가 끝나는 시간을 업데이트 해주는 것이므로 findmin + decreasekey 의 연산을 통해 수행할 수 있습니다. $O(1) + O(log \; n)$

 

 

따라서 현재 교실이 d개일 때, 강의 하나를 배치하는데 최대 $O(log \; d)$ 시간이 소요됩니다.

 

 

따라서 알고리즘의 총 수행 시간은 $O(n \; log \; n)$ 으로 줄어들 수 있습니다.