计算机算法设计与分析(第3版)[王晓东编著][电子教案第4章(10)

计算机算法设计与分析(第3版)[王晓东编著][电子教案

4.1 活动安排问题若被检查的活动i的开始时间Si小于最近选择的活 动j的结束时间fi,则不选择活动i,否则选择活动i加 入集合A中。 贪心算法并不总能求得问题的整体最优解。但对 于活动安排问题，贪心算法greedySelector却总能求 得的整体最优解，即它最终所确定的相容活动集合A的 规模最大。这个结论可以用数学归纳法证明。