计算机算法设计与分析(第3版)[王晓东编著][电子教案
4.1 活动安排问题由于输入的活动以其完成时间的非减序排列， 所以算法greedySelector每次总是选择具有最早 完成时间的相容活动加入集合A中。直观上，按这 种方法选择相容活动为未安排活动留下尽可能多 的时间。也就是说，该算法的贪心选择的意义是 使剩余的可安排时间段极大化，以便安排尽可能 多的相容活动。 算法greedySelector的效率极高。当 输入的活动已按结束时间的非减序排列，算法只 需O(n)的时间安排n个活动，使最多的活动能相
容 地使用公共资源。如果所给出的活动未按非减序 排列，可以用O(nlogn)的时间重排。7