问题：设有n个活动的集合E＝{1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si＜fi。如果选择了活动i，则它在半开时间区间[si ，fi )内占用资源。若区间[si ，fi )与区间[sj，fj )不相交，则称活动i与活动j是相容的。当 si ≥ fj 或 sj ≥ fi 时，活动i与活动j相容。 活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。
#include <iostream> #include<vector> #include<algorithm> using namespace std; struct action{ int s; //起始时间 int f; //结束时间 int index; //活动的编号 int select; void display() { cout<<"活动"<<index<<"被安排"<<endl; } }; action a[1000]; bool cmp(const action &a, const action &b) { if (a.f<=b.f) return true; return false; } void Greedy(action v[],int n){ v[0].select=1; int select=0; for(int i=1;i<n;i++) { if(v[i].s>=v[select].f){ v[i].select=1; select=i; } } cout<<"可以安排如下的活动："<<endl; for(int i=0;i<n;i++) if(v[i].select) v[i].display(); } int main() { for(int i = 0;i<5;i++) {cin>>a[i].s>>a[i].f; a[i].index=i+1; a[i].select=0; } sort(a, a+5, cmp); Greedy(a,5); return 0; }