template
/*** [GreedySelector 活动安排贪心算法]* @param n      [活动总数量, 此处默认n>=2]* @param start  [开始时间数组]* @param finish [结束时间数组]* @param mark   [是否被选中标记数组]*/
void GreedySelector(int n, Type start[], Type finish[], bool mark[]){int j = 1; // 最后一个被选中的下标;mark[j] = true;for(int i=2; i<=n; i++){if(start[i]>=finish[j]){mark[i] = true;j = i;}else{mark[i] = false;}}
}
/**[活动安排问题描述]* 假设n个活动的集合为 			E = {i| i=1,2,..., n}* 开始时间集合 			start = {s1, s2, ..., sn}* 结束时间集合 		   finish = {f1, f2, ..., fn}      其中 finish 是非降序列 即 i fi <= fj	* 现在要求一个活动安排集合mark, 对于mark中的任意活动i,j,要求 fi<=sj 或者 fj<=si* =================================================================================================================================* 结论: 在活动安排问题中, 贪心选择算法一定能得到全局最优解* =================================================================================================================================* 证明步骤:* Target 1. 证明总是存在以贪心选择开始的最优活动安排方案;* Target 2. 证明对于做出贪心选择后, 原问题等价于"对剩余与贪心选择活动相容的活动进行安排的问题"*    		即证明若E是总的活动集合, 那么A是原活动集合E的最优安排,那么A' = A-{1} 是活动 E' = {i∈E| start[i] >= finish[1]} 的最优解*=================================================================================================================================* 证明如下:* 1.[Target 1]*   假设 P是活动E的一个最优解, 而P中的第一个活动是k. *   若k为1, 那么此P即为以贪心选择开始的活动安排,即证;*   否则, 活动安排P的第一个活动k>1, 现在考虑构造一个活动安排Q=P-{k}+{1},*   由于finish[1]<=finish[k](finish列表非降), 又由于P是一个合法的活动安排,因此Q也是一个合法的活动安排,且活动安排数量一致;*   因此P是最优解=>Q为最优解 => 活动安排Q是以贪心选择开始的活动安排.** 2.[Target 2]*   假设P是活动E的一个以贪心选择开始的最优解, 那么现在考虑 E中兼容活动{1}的所有活动的集合活动 E' = {i∈E| start[i] >= finish[1]}*   我们有 P' = P-{1} 是 E'的一个活动安排, 我们要证明P'是最优的活动安排:*   		假设 Q 是活动E'的一个最优解, 假设它具有比P'更多的活动, 那么将活动{1}加入Q, 那么将得到活动集合E的一个最优解Q+{1}*   		则|Q+{1}| = |Q|+1 > |P'|+1 = |P-{1}| + 1 = |P| 因此 对于活动集合E来说 Q+{1} 是比 P 更优的解,矛盾.**   综合上述两点可以知道, 对于活动安排问题,贪心算法得到的是全局最优解.*=================================================================================================================================*/