贪心算法 | 高级钟点秘书——会议安排
3、高级钟点秘书——会议安排
某跨国公司总裁正分身无术，为一堆会议时间表焦头烂额，希望高级钟点秘书能做出合理的安排，能在有限的时间内召开更多的会议。
3.1问题分析
在会议安排中，每个会议 i 都有起始时间 bi 和结束时间 ei ，且 bi < ei ，即一个会议进行的时间为半开区间 [bi , ei)。如果 [bi , ei)和[bj , ej) 均在“有限时间内”，且不相交，则称会议 i 和会议 j 相容的。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，尽可能在有限时间内召开更多的会议。其中会议时间表如下表所示：
会议i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
开始时间bi |
3 |
1 |
5 |
2 |
5 |
3 |
8 |
6 |
8 |
12 |
结束时间ei |
6 |
4 |
7 |
5 |
9 |
8 |
11 |
10 |
12 |
14 |
要让会议数最多，我们需要选择最多的不相交时间段。我们可以尝试贪心策略：
（1）每次选择开始时间最早且与已安排的会议相容的会议；（不行）（2）每次选择持续时间最短且与已安排的会议相容的会议；（不行）（3）每次选择结束时间最早且与已安排的会议相容的会议。（行）
例如：对于（1）来说，8点开始，却要持续12个小时，这样一天只能安排一个会议；如果选择持续时间短，则可能开始时间晚，例如19点开始，20点结束，这样也只能安排一个会议；所以我们尽量选择那些开始时间要早，而且持续时间短的会议，也就是结束时间最早的会议。
3.2算法设计
（1）数据初始化，将n个会议的开始时间、结束时间存放在结构体数组中，然后按结束时间从小到大排序，结束时间相等的，按开始时间从大到小排序。
（2）选择第一个具有最早结束时间的会议， 用 last 记录刚选中会议的结束时间。
（3）依次从剩下未安排的会议中选择，若会议 i 开始时间大于等于最后一个选中的会议的结束时间 last ，那么会议 i 与已选中的会议相容，可以安排，更新 last 为刚选中会议的结束时间；否则，舍弃会议 i ，检查下一个会议是否可以安排。
3.3图解算法
1、原始会议时间表：
会议i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
开始时间bi |
3 |
1 |
5 |
2 |
5 |
3 |
8 |
6 |
8 |
12 |
结束时间ei |
6 |
4 |
7 |
5 |
9 |
8 |
11 |
10 |
12 |
14 |
2、排序后的会议时间表：
会议i |
2 |
4 |
1 |
3 |
6 |
5 |
8 |
7 |
9 |
10 |
开始时间bi |
1 |
2 |
3 |
5 |
3 |
5 |
6 |
8 |
8 |
12 |
结束时间ei |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
14 |
3、贪心选择过程
（1）首先选择排序后的第一个会议即最早结束的活动（编号为2），用last记录最后一个被选中活动的结束时间last=4。
（2）检查剩余的会议，找到第一个开始时间大于等于last(last=4)的会议，子问题转化为该会议开始，余下所有的会议，如下表所示：
会议i |
2 |
4 |
1 |
3 |
6 |
5 |
8 |
7 |
9 |
10 |
开始时间bi |
1 |
2 |
3 |
5 |
3 |
5 |
6 |
8 |
8 |
12 |
结束时间ei |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
14 |
从子问题中，选择第一个会议即最早结束的会议（编号为3），更新last为刚选中活动的结束时间last=7
（3）检查剩余的会议，找到第一个开始时间大于等于last(last=7)的会议，子问题转化为该会议开始，余下所有的会议，如下表所示：
会议i |
2 |
4 |
1 |
3 |
6 |
5 |
8 |
7 |
9 |
10 |
开始时间bi |
1 |
2 |
3 |
5 |
3 |
5 |
6 |
8 |
8 |
12 |
结束时间ei |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
14 |
从子问题中，选择第一个会议即最早结束的会议（编号为7），更新last为刚选中活动的结束时间last=11
（4）检查剩余的会议，找到第一个开始时间大于等于last(last=11)的会议，子问题转化为该会议开始，余下所有的会议，如下表所示：
会议i |
2 |
4 |
1 |
3 |
6 |
5 |
8 |
7 |
9 |
10 |
开始时间bi |
1 |
2 |
3 |
5 |
3 |
5 |
6 |
8 |
8 |
12 |
结束时间ei |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
14 |
从子问题中，选择第一个会议即最早结束的会议（编号为10），更新last为刚选中活动的结束时间last=14，所有会议检查完毕，算法结束。
4、构造最优解
从贪心选择的结果，可以看出，被选中的会议编号为{2,3,7,10}，可以安排的会议数量最多为4.
3.4伪代码详解
（1）数据结构定义
结构体meet中定义了beg表示会议的开始时间，end表示会议的结束时间，会议的meet数据结构：
struct Meet{int beg;//会议开始的时间int end;//会议结束的时间int num;//记录会议的编号}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);//对会议按cmp指标排序
（3）贪心算法求解
在会议按结束时间降序排序的基础上，首先选中第一个会议，用last变量记录刚刚被选中会议的结束时间。下一个会议的开始时间与last比较，如果大于等于last，则选中。每次选中一个会议，更新last为最后一个被选中会议的结束时间，被选中的会议数ans加1。如果会议的开始时间不大于等于last，继续考察下一个会议，直到所有会议考察完毕。
int ans=1;//用来记录可以安排会议的个数，初始时选中了第一个会议int last=meet[0].end;//记录刚刚被选中会议的结束时间for(i=0;i<n;i++)//依次检查每一个会议{if(meet[i].beg>=last)//如果会议i开始时间大于等于最后一个选中的会议的结束时间{ans++;last=meet[i].end;//更新last为最后一个选中会议的结束时间}}return ans;