**
** 设有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相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： 贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中
#include <iostream> using namespace std; template<class Type> void GreedySelector(int n, Type s[], Type f[], bool A[])//n是活动个数，s是开始时间，f是结束时间，A是活动状态 { A[1]=true; int j=1;//记录最近一次加入A中的活动 for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容 { if (s[i]>=f[j]) { A[i]=true; j=i; } else { A[i]=false; } } } int Partition(int *b,int *a,int p,int r) ; //快速排序 void QuickSort(int *b,int *a,int p,int r) { if(p<r) { int q=Partition(b,a,p,r); QuickSort(b,a,p,q-1);/*对左半段排序*/ QuickSort(b,a,q+1,r);/*对右半段排序*/ } } //产生中间数 int Partition(int *b,int *a,int p,int r) { int k,m,i=p,j=r+1; int x=a[p],y=b[p]; while(1) { while(a[++i]<x); while(a[--j]>x); if(i>=j) break; else { k=a[i];a[i]=a[j];a[j]=k; m=b[i];b[i]=b[j];b[j]=m; } } a[p]=a[j]; b[p]=b[j]; a[j]=x; b[j]=y; return j; } int count; int main() { //存储开始时间 int s[100]; //存储结束时间 int f[100]; bool A[100];//存储各个活动的可选状态 cout<<"输入活动个数:"; cin>>count; for(int i=1;i<=count;i++){ cout<<"输入s["<<i<<"]:"; cin>>s[i]; cout<<"输入f["<<i<<"]:"; cin>>f[i]; cout<<endl; } QuickSort(s,f,0,count); //输出快排后 for(int i=1;i<=count;i++) { cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl; } GreedySelector(count,s,f,A); cout<<"安排的活动序号为："<<endl; //输出活动序号 for(int i=1;i<=count;i++) { if(A[i]){ cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl; } } system("pause"); return 0; }运行结果
