> 是不是两次对要求"至少为1"的问题进行贪心?
> 用贪心过了的高手能讲讲吗? 先谢过了

  先将区间按左端点Left升序为第一关键字, 右端点Right降序为第二关键字排序。再在线性时间内去除包含关系：即若A包含B，则去除A，因为B满足了，A必然也满足。

       最后贪心，尽量向后安排满足点。设置2根扫描线i, j，表示最后两个满足点，不妨设i < j。从左到右扫描，每找到一个未被满足的区间S，即i<S.Left。若j<S.Left，即i, j都不在区间S中，则设置i, j为S的最后两个数，即i’ = S.Right – 1, j’ = S.Right；否则，即只有j在区间S中，则设置j为S的最后一个数, 即j’ = S.Right，但是要维护i<j的性质，所以令i’ = j。证明方法也很简单，对于任何的最优解，若第一个区间不在两个最右点取，可以调整到这两个最右点，并且解不会更差。所以贪心是正确的。

• 这样排序不行！ 若第二步要尽量向后安排，则排序时应该先按右端点Right升序，再左端点Left降序， 对吧！ (0) alpc47 2008-10-31 20:17:11