An activity-selection problem

16.1-2

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

->

시작 시간이 가장 늦은 activity를 선택하고 해당 activity의 시작 시간보다 끝나는 시간이 더 큰 activity를 제외한 나머지 activity들로 subset을 구성한 뒤 다시 그 중 시작 시간이 가장 늦은 activity를 선택하는 행동을 반복한다. 주어진 상황에서 최적의 답을 선택하고 나머지 subset 에서 다시 최적을 선택하는 행위를 반복하면서 주어진 문제를 해결할 수 있기 때문에 이는 greedy 알고리즘이다.

-

Activity-selection problem 에서 S 가 시작하는 시간이 가장 늦은 activity 부터 가장 빠른 activity 까지 순서대로 정렬되어 있다고 가정한다.

S에서 시작 시간이 가장 늦은 activity를 am 라고 한다.

S에서 파생되는 임의의 maximum-size subset을 Ak 라고 한다. 그리고 이 Ak에서 시작 시간이 가장 늦은 activity를 aj라고 한다.

만약 am == aj 라면, S의 첫 번째 원소가 Ak의 첫 번째 원소이기 때문에 (시작 시간이 가장 늦은) 이야기는 끝난다.

만약 am != aj 라면, Ak에서 aj를 빼고 am을 넣은 또 다른 subset A'k를 구성한다.

이 때 startTime of am >= startTime of aj 이기 때문에, Ak의 activity들의 시간이 겹치지 않았다면, A'k의 시간도 겹칠 수 없게 된다. A'k의 나머지 원소들의 끝나는 시간은 당연히 aj와 am의 시작 시간보다 빠를 것이기 때문에. 따라서 여전히 A'k는 maximum-size subset이고, A'k는 am을 포함하는 S의 maximum-size subset이라고 할 수 있다. 따라서 earliest start time activity를 선택하는 greedy 알고리즘은 항상 maximum-size subset을 구성할 수 있다.

16.1-3 

Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time.

->

가장 시간이 짧은 activity를 선택하는 경우
A: 0~5
B: 4~7
C: 6~10
이 경우 가장 시간이 짧은 B를 먼저 선택한다면 시간은 가장 짧지만 다른 두 activity의 중간에 겹치고 시간이 짧은 것을 선택함으로 인해서 생기는 공간에 들어갈 수 있는 다른 activity가 없으므로 maximum-size subset을 구할 수 없게 된다.

-

가장 겹치는 activity가 적은 activity를 선택하는 경우

      |--------|                   |-------|
      |--------|                   |-------|
      |--------|                   |-------|
|---------|  |---------| |----------| |--------|
                    |--------|
위 그림과 같이 optimal maximum-size subset 사이에 불필요한 blocker가 있어서 overlap 개수를 높이고, 그 blocker와 겹치지 않은 activity가 있다면 해당 activity가 optimal choice가 아님에 도 불구하고 선택되는 현상이 발생할 수 있다.

-

시작 시간이 가장 빠른 activity를 선택하는 경우

간단하게 반례를 찾을 수 있다. 시작 시간이 가장 빠른 activity가 만약 모든 사용 가능 시간을 점유하는 경우 (끝나는 시간이 가장 길다면) optimal 하지 않다.