共有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