继续一道贪心算法的问题
有N个学生，每个学生在(Si,Ei)时间段内有任务，我们想从中选K个学生，使得这K个学生可以观察其他N-K个学生的工作。例如有三个学生（1，5）（2，3）（4，6），那么就选择（1，5）,可以监视（2，3） （4，6）
[解决办法]
1)对结束时间最早的学生a1,求跟其有时间交叉,且结束时间最大的学生aj;
2)对aj无法监视的学生中结束时间最早的学生a1' ,求跟其有时间交叉,且结束时间最大的学生aj';
直到所有学生都被监视或选中,否则继续2);
[解决办法]
这么一来应该是没问题了，贪心算法的正确性证明：
还是按照每个学生的任务结束时间升序排列：S={1,2,3,...,n}
假设用这种贪心算法得到的监视学生为i[1],i[2],...,i[k]，这里1<=i[1]<i[2]<……<i[k]<=n
1.第一步，先来证明总存在一个以i[1]开头的最优解.
假设A为S的一个子集，同时A是一个最优解，假设A={j[1],j[2],...,j[t]}，这里1<=j[1]<j[2]<……<j[t]<=n
首先必须满足j[1]<=i[1]。否则的话，根据贪心算法过程就可以推断出来，学生1没有被监视到。
如果i[1]==j[1]，那么一切好说；
如果i[1]>j[1]，就在集合A中把j[1]替换成i[1]。
凡是m<＝i[1]，学生m都能被学生i[1]监视到。又因为i[1]的结束时间大于m的结束时间，所以凡是m能监视到的学生，i[1]都能监视到（分m与1相交和不相交两种情况来讨论比较容易理解）。也就是说j[1]能干的活，i[1]都能包了，因此用i[1]来替换j[1]还是能监视其余所有的学生。
因此A-{j[1]}+{i[1]}仍然是一个最优解。
【实际上这里还有一个小问题要澄清，那就是j[2],...j[t]中会不会出现与i[1]重复的值？答案是不会的。
因为前面已经提到了凡是m<=i[1]，m能监视的学生i[1]都能监视到，因此我们担心的情况与A是最优解相矛盾，不会出现】
2.第二步，来证明A-{i[1]}=={j[2],...,j[t]}就是“i[1]无法监视到的学生”的一个最优解。
这一步用反证法来说明：如果存在一个比集合A-{i[1]}更少的方案就能监视到所有“i[1]无法监视到的学生”，那么这个方案再加上i[1]，就能监视到所有的学生，这与A是最优解是矛盾的.
以上2步合起来就能说明，每进行一次贪心选择就可以得到一个最优解。
