贪心算法是期望通过局部最优选择从而得到全局最优的解决方案，通常能得到许多问题的整体最优解或整体最优解的近似解。

利用贪心算法求解的问题往往具有贪心选择性质和最优子结构。

贪心选择性质是指原问题的整体最优解可以通过一系列的局部最优的选择得到。应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运行贪心策略解决的问题在程序的运行过程中无回溯过程。

最优子结构是指当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

另外，此类问题往往也有多个贪心策略可供选择，选择什么样的贪心策略直接决定算法的好坏。

本文以能在有限的时间内召开更多的会议做为实例进行讲解。

1　问题分析、选择贪心策略

在有限的时间内召开更多的会议是一个典型的会议安排问题，会议安排的目的是能在有限的时间内召开更多的会议（任何两个会议不能同时进行）。在会议安排中，每个会议i都有起始时间bi和结束时间ei，且bi<ei，即一个会议进行的时间为半开区间[bi，ei）。如果[bi，ei）与[bj，ej）均在“有限的时间内”，且不相交，则称会议i与会议j相容的。也就是说，当bi≥ej或bj≥ei时，会议i与会议j相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。

在这个问题中，“有限的时间内（这段时间应该是连续的）”是其中的一个限制条件，也应该是有一个起始时间和一个结束时间（简单化，起始时间可以是会议最早开始的时间，结束时间可以是会议最晚结束的时间），任务就是实现召开更多的满足在这个“有限的时间内”等待安排的会议，如下图所示：

从上图可以看出，{会议1，会议4，会议6，会议8，会议9}，{会议2，会议4，会议7，会议8，会议9}都是能安排最多的会议集合。

要让会议数最多，我们需要选择最多的不相交时间段。我们可以尝试贪心策略：

（1）每次从剩下未安排的会议中选择会议具有最早开始时间且与已安排的会议相容的会议安排，以增大时间资源的利用率。（2）每次从剩下未安排的会议中选择持续时间最短且与已安排的会议相容的会议安排，这样可以安排更多一些的会议。（3）每次从剩下未安排的会议中选择具有最早结束时间且与已安排的会议相容的会议安排，这样可以尽快安排下一个会议。

思考一下，如果选择最早开始时间，则如果会议持续时间很长，例如8点开始，却要持续12个小时，这样一天就只能安排一个会议；如果选择持续时间最短，则可能开始时间很晚，例如19点开始，20点结束，这样也只能安排一个会议，所以我们最好选择那些开始时间要早，而且持续时间短的会议，即最早开始时间+持续时间最短，就是最早结束时间。

因此采用第（3）种贪心策略，每次从剩下的会议中选择具有最早结束时间且与已安排的会议相容的会议安排。

2　算法设计

（1）初始化：将n个会议的开始时间、结束时间存放在结构体数组中（想一想，为什么不用两个一维数组分别存储？），如果需要知道选中了哪些会议，还需要在结构体中增加会议编号，然后按结束时间从小到大排序（非递减），结束时间相等时，按开始时间从大到小排序（非递增）；

（2）根据贪心策略选择第一个具有最早结束时间的会议，用last记录刚选中会议的结束时间；

（3）选择第一个会议之后，依次从剩下未安排的会议中选择，如果会议i开始时间大于等于最后一个选中的会议的结束时间last，那么会议i与已选中的会议相容，可以安排，更新last为刚选中会议的结束时间；否则，舍弃会议i，检查下一个会议是否可以安排。

3 完美图解

3.1 原始的会议时间表和排序后的会议时间表：

3.2 贪心选择过程

（1）首先选择排序后的第一个会议即最早结束的会议（编号为2），用last记录最后一个被选中会议的结束时间，last=4。

（2）检查余下的会议，找到第一个开始时间大于等于 last（last=4）的会议，子问题转化为从该会议开始，余下的所有会议。如表3所示。

从子问题中，选择第一个会议即最早结束的会议（编号为3），更新last为刚选中会议的结束时间last=7。

（3）检查余下的会议，找到第一个开始时间大于等于last（last=7）的会议，子问题转化为从该会议开始，余下的所有会议。如表4所示↑。

从子问题中，选择第一个会议即最早结束的会议（编号为 7），更新 last 为刚选中会议的结束时间last=11。

（4）检查余下的会议，找到第一个开始时间大于等于last（last=11）的会议，子问题转化为从该会议开始，余下的所有会议。如表5所示。

从子问题中，选择第一个会议即最早结束的会议（编号为10），更新last为刚选中会议的结束时间last=14；所有会议检查完毕，算法结束。如表6所示↑。

3.4 构造最优解

从贪心选择的结果，可以看出，被选中的会议编号为{2，3，7，10}，可以安排的会议数量最多为4，如表6所示↑。

4　重点代码详解

（1）数据结构定义

以下C++程序代码中，结构体meet中定义了beg表示会议的开始时间，end表示会议的结束时间，会议meet的数据结构：

struct Meet{int beg; //会议的开始时间int end; //会议的结束时间} meet[1000]；

（2）对会议按照结束时间非递减排序

我们采用C++中自带的sort函数，自定义比较函数的办法，实现会议排序，按结束时间从小到大排序（非递减），结束时间相等时，按开始时间从大到小排序（非递增）：

bool cmp(Meet x,Meet y){if(x.end==y.end) //结束时间相等时return x.beg>y.beg; //按开始时间从大到小排序return x.end<y.end; //按结束时间从小到大排序}sort(meet,meet+n,cmp);

（3）会议安排问题的贪心算法求解

在会议按结束时间非递减排序的基础上，首先选中第一个会议，用last变量记录刚刚被选中会议的结束时间。下一个会议的开始时间与last比较，如果大于等于last，则选中。每次选中一个会议，更新last为最后一个被选中会议的结束时间，被选中的会议数ans加1；如果会议的开始时间不大于等于last，继续考查下一个会议，直到所有会议考查完毕。

上面介绍的程序中，只是返回了可以安排的会议最大数，而不知道安排了哪些会议，这显然是不满足需要的。我们可以改进一下，在会议结构体meet中添加会议编号num变量，选中会议时，显示选中了第几个会议。

5　编码

输入

输入会议总数：10输入会议的开始时间和结束时间，以空格分开：8 109 1110 1511 1413 1614 1715 1717 1818 2016 19

输出

排完序的会议时间如下：会议编号 开始时间 结束时间 1 8 10 2 9 11 4 11 14 3 10 15 5 13 16 7 15 17 6 14 17 8 17 18 10 16 19 9 18 20-------------------------------------------------选择的会议的过程： 选择第1个会议 选择第4个会议 选择第7个会议 选择第8个会议 选择第9个会议

使用上面贪心算法可得，选择的会议是第2、3、7、10个会议，输出最优值是4。

6　算法解析及优化拓展

6.1 算法复杂度分析

（1）时间复杂度：在该算法中，问题的规模就是会议总个数n。显然，执行次数随问题规模的增大而变化。首先在成员函数setMeet::init()中，输入n个结构体数据。输入作为基本语句，显然，共执行n次。而后在调用成员函数setMeet::solve()中进行排序，易知sort排序函数的平均时间复杂度为O(nlogn)。随后进行选择会议，贡献最大的为if(meet[i].beg>=last)语句，时间复杂度为O(n)，总时间复杂度为O(n +nlogn)= O(nlogn)。

（2）空间复杂度：在该算法中，meet[]结构体数组为输入数据，不计算在空间复杂度内。辅助空间有i、n、ans等变量，则该程序空间复杂度为常数阶，即O(1)。

6.2 算法优化拓展

想一想，你有没有更好的办法来处理此问题，比如有更小的算法时间复杂度？

参考：

附源代码：

#include <iostream>#include <algorithm>#include <cstring>using namespace std;struct Meet{ int beg;		//会议的开始时间 int end;		//会议的结束时间 int num;		//记录会议的编号}meet[1000];		//会议的最大个数为1000 class setMeet{ public: void init(); void solve(); private: int n,ans;		// n:会议总数 ans: 最大的安排会议总数}; //读入数据void setMeet::init(){ int s,e; cout <<"输入会议总数："<<endl; cin >> n; int i; cout <<"输入会议的开始时间和结束时间，以空格分开："<<endl; for(i=0;i<n;++i) { cin>>s>>e; meet[i].beg=s; meet[i].end=e; meet[i].num=i+1; }} bool cmp(Meet x,Meet y){ if (x.end == y.end) return x.beg > y.beg; return x.end < y.end;} void setMeet::solve(){ sort(meet,meet+n,cmp);								//对会议按结束时间排序 cout <<"排完序的会议时间如下："<<endl; int i; cout <<"会议编号"<<" 开始时间 "<<" 结束时间"<<endl; for(i=0; i<n;i++) { cout<< " " << meet[i].num<<"\t\t"<<meet[i].beg <<"\t"<< meet[i].end << endl; } cout <<"-------------------------------------------------"<<endl; cout << "选择的会议的过程：" <<endl; cout <<" 选择第"<< meet[0].num<<"个会议" << endl;	//选中了第一个会议 ans=1; int last = meet[0].end;							//记录刚刚被选中会议的结束时间 for( i = 1;i < n;++i) { if(meet[i].beg>=last) {						//如果会议i开始时间大于等于最后一个选中的会议的结束时间 ans++; last = meet[i].end;						//更新比较条件last cout <<" 选择第"<<meet[i].num<<"个会议"<<endl; } } cout <<"最多可以安排" <<ans << "个会议"<<endl;} int main(){ setMeet sm; sm.init();					//读入数据 sm.solve();					//贪心算法求解 system("pause"); return 0;}

－End－