활동 선택 문제

시작 시간과 종료 시간과 함께 n개의 다른 활동이 제공됩니다. 한 사람이 해결할 수 있는 최대 활동 수를 선택합니다. 나머지 활동 중 종료 시간이 최소이고 시작 시간이 마지막으로 선택한 활동의 ​​종료 시간보다 크거나 같은 다음 활동을 찾기 위해 탐욕적 접근 방식을 사용합니다.

• 이 문제의 복잡성은 목록이 정렬되지 않은 경우 O(n log n)입니다.
• 정렬된 목록이 제공되면 복잡성은 O(n)이 됩니다.

입력 및 출력

Input:
A list of different activities with starting and ending times.
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
Output:
Selected Activities are:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9

알고리즘

maxActivity(act, size)

입력: 활동 목록 및 목록의 요소 수입니다.

출력 - 활동 순서가 어떻게 선택되었는지.

Begin
   initially sort the given activity List
   set i := 1
   display the ith activity //in this case it is the first activity

   for j := 1 to n-1 do
      if start time of act[j] >= end of act[i] then
         display the jth activity
         i := j
   done
End

예시

#include<iostream>
#include<algorithm>
using namespace std;

struct Activitiy {
   int start, end;
};

bool comp(Activitiy act1, Activitiy act2) {
   return (act1.end < act2.end);
}

void maxActivity(Activitiy act[], int n) {
   sort(act, act+n, comp); //sort activities using compare function

   cout << "Selected Activities are: " << endl;
   int i = 0;// first activity as 0 is selected
   cout << "Activity: " << i << " , Start: " <<act[i].start << " End:
      " << act[i].end <<endl;

   for (int j = 1; j < n; j++) { //for all other activities
      if (act[j].start >= act[i].end) { //when start time is >= end
         time, print the activity
         cout << "Activity: " << j << " , Start: " <<act[j].start << " End: " << act[j].end <<endl;
         i = j;
      }
   }
}

int main() {
   Activitiy actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
   int n = 6;
   maxActivity(actArr,n);
   return 0;
}

출력

Selected Activities are:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9