활동 선택 문제(activity selection problem)

Greedy 알고리즘의 첫 번째 예제는 활동선택문제(Activity Selection Problem) 이다. 
활동선택은 먼저 시작(start)과 끝(finish) 시간이 n 개의 활동이 주어진다. 
개인이 한 번에 하나의 활동에만 작업(즉 겹치는 시간에는 동일한 활동을 할 수 없다는 뜻) 할 수 있다고 가정 할 때 한 사람이 수행 할 수있는 최대 활동 수를 선택하는 문제라고 본다.

그림1. 활동 선택 문제 예

[출처]  https://aleen42.github.io/PersonalWiki/Algorithmn/Analysis/Greedy/Activity/Activity.html

 

예를들어 A라는 영업사원이 판매를 위해 a,b,c, 3개 업체와 미팅을 해야하는데 각 회의이 시작 시간과 회의 종료시간이 다음과 같다고 할때 A영업사원은 최대한 많은 업체와 미팅을 하기위해 어떤 업체를 선택할 수 있는가 ? 단, 회의는 겹치면 안된다.

 s_i[] =  {1, 2, 2};
 f_i[] =  {2, 5, 3};

 이 예제에서는 A 사원이 최대로 참여할 수 있는 상황은 1시-2시 미팅과, 2시-3시 미팅 2개이다. 

 

활동선택 문제는 그리디 알고리즘으로 풀수 있는데 젤먼저 활동 중에서 종료 시간(finish time이 가장 적고 시작 시간이 이전에 선택한 활동의 ​​종료 시간보다 크거(greater)나 같은(equal) 다음 활동을 항상 선택하는 것이다.
왜냐면 욕심쟁이는 매순간 활동이 빨리 끝날 것부터 선택해야 나머지 활동들을 선택할 확률이 높아지기 때문이다.

알고리즘은 매우 심플한데 아래와 같다. 

활동선택문제 알고리즘

1. 각 활동들을 완료시간 기준으로 오름차순으로 정렬한다. 오름차순으로 정렬하는것은 활동이 가장 빨리 끝나는것부터 선택하려 하기 때문이다.
2. 정렬된 활동들중 첫 번째 활동을 선택한다.
3. 정렬된 활동들중 나머지 활동에 대해 이 활동의 ​​시작 시간이 이전에 선택한 활동의 ​​종료 시간보다 크거나 같으면이 활동을 선택하도록 한다.

 

 
public class ActivitySelectionMain {
 
 
    // Prints a maximum set of activities that can be done by a single 
    // person, one at a time. 
    //  n   -->  Total number of activities 
    //  s[] -->  An array that contains start time of all activities 
    //  f[] -->  An array that contains finish time of all activities 
    public static void printMaxActivities(int s[], int f[], int n) {
        int i, j;
 
        System.out.print("Following activities are selected : n");
 
        // The first activity always gets selected 
        i = 0;
        System.out.print(i + " ");
 
        // Consider rest of the activities 
        for (j = 1; j < n; j++) {
            // If this activity has start time greater than or 
            // equal to the finish time of previously selected 
            // activity, then select it 
            if (s[j] >= f[i]) {
                System.out.print(j+" ");
                i = j;
            }
        }
    }
 
    // driver program to test above function 
    public static void main(String[] args)  {
        int s[] =  {1, 3, 0, 5, 8, 5};
        int f[] =  {2, 4, 6, 7, 9, 9};
        int n = s.length;
 
        printMaxActivities(s, f, n);
    }
 
 
 
}