C++의 활동 선택 문제(Greedy Algo-1)?

시작 시간과 종료 시간과 함께 n개의 다른 활동이 제공됩니다. 한 사람이 해결할 수 있는 최대 활동 수를 선택하십시오.

나머지 활동 중 종료 시간이 최소이고 시작 시간이 마지막으로 선택한 활동의 ​​종료 시간보다 크거나 같은 다음 활동을 찾기 위해 탐욕적 접근 방식을 사용합니다.

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

입력

시작 및 종료 시간이 포함된 다양한 활동 목록입니다.

{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}

출력

선택한 활동은 -

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(액트, 크기)

입력 - 활동 목록 및 목록의 요소 수.
출력 - 활동 순서가 어떻게 선택되었는지.

Begin
   initially sort the given activity List
   set i := 1
   display the i-th 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