C ++でのアクティビティ選択問題（欲張り法-1）？

開始時間と終了時間でnの異なるアクティビティが与えられます。 1人で解決するアクティビティの最大数を選択します。

貪欲なアプローチを使用して、残りのアクティビティの中で終了時間が最小で、開始時間が最後に選択したアクティビティの終了時間以上である次のアクティビティを見つけます。

• この問題の複雑さは、リストがソートされていない場合の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（act、size）

入力 -アクティビティのリスト、およびリスト内の要素の数。
出力 -アクティビティの順序はどのように選択されたか。

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