在本章中，我们将通过示例和使用方法学习如何解决活动选择问题 贪心法.
问题陈述：
您将获得活动列表以及开始和结束时间。您的工作是查找该机器可以执行的最大活动数。请注意，机器一次只能执行一项任务。
这些活动应无冲突。这意味着，新活动的开始时间应大于或等于上一个活动的结束时间。
例如：
以下是活动的开始和结束时间列表；
现在可以选择活动a1，但是不能选择a2，因为a2的开始时间小于a1的结束时间。因此，您跳过a2并移至a3。
由于a3的开始时间大于a1的时间，因此您将选择它。但是是最佳解决方案吗？没有
因为，如果选择a2，则为a3。然后，您将完成更多工作。
那么如何解决这个问题呢？
我们可以通过解决 贪心法。我们按照以下3个步骤进行操作，以找到解决方案。
步骤1：根据结束时间按升序对活动进行排序。
步骤2：选择该活动
步骤3：检查新活动的开始时间是否大于或等于上一个活动的结束时间，然后选择它。重复步骤2和3，直到检查了所有活动。
请看下表：
现在根据结束时间对活动进行排序
现在选择a1并将其放在结果表中
现在，a2开始时间小于a1结束时间。因此跳过a2。
现在，a6开始时间大于a1结束时间。因此，选择该活动。
同样，a4开始时间小于a6结束时间。因此，将其丢弃。
a3开始时间等于a6结束时间。因此，选择该活动。
a5开始时间等于a3结束时间。因此选择它。
因此，最终结果。
C ++中活动选择问题的解决方案
#include <iostream>
using namespace std;
struct Activity
{
char id[10];
int start;
int finish;
};
void activitySelection(Activity activities[], int n)
{
int i, j;
Activity temp;
// sort activities in ascending order according to their ascending order
for(i = 1; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(activities[j].finish > activities[j+1].finish)
{
temp = activities[j];
activities[j] = activities[j+1];
activities[j+1] = temp;
}
}
}
cout<<"Activities printed according to sorted order of their finishing time."<<endl;
cout<<"Activity Start Finish"<<endl;
for(i = 0; i < n; i++)
{
cout<<activities[i].id<<" "<< activities[i].start<<" " <<activities[i].finish<<endl;
}
cout<<"Final Result"<<endl;
cout<< "Activity Start Finish"<<endl;
cout<< activities[0].id<<" " << activities[0].start<<" " <<activities[0].finish<<endl;
//check and select the next activity whose start time is greater than or equal to the finishing period of previous
//activity
i = 0;
for(j = 1; j < n; j++)
{
if(activities[j].start >= activities[i].finish)
{
cout<<activities[j].id<<" "<< activities[j].start<<" "<< activities[j].finish<<endl;
i = j;
}
}
}
int main(void) {
Activity activities[8] =
{
{"a1", 2, 3},
{"a2", 1, 4},
{"a3", 8, 10},
{"a4", 6, 9},
{"a5", 10, 15},
{"a6", 5, 8},
};
int total_activity = 6;
activitySelection(activities, total_activity);
return 0;
}
输出：
Activities printed according to sorted order of their finishing time. Activity Start Finish a1 2 3 a2 1 4 a6 5 8 a4 6 9 a3 8 10 a5 10 15 Final Result Activity Start Finish a1 2 3 a6 5 8 a3 8 10 a5 10 15
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
