1211 - 不重叠的线段

如果线段是杂乱无章的，枚举所有线段选与不选的情况，那么复杂度是 O(2^n) ，无法接受。
首先明确一个问题：假设有两个区间 x,y，区间 x 完全包含 y 。
那么， 选 x 是不划算的，因为 x 和 y 最多只能选一个，选 x 还不如选 y ，这样不仅区间数目不会减少，而且给其他区间留出了更多的位置。
接下来，按照 bi 从小到大的顺序给区间排序。
贪心策略是：一定要选第一个区间。为什么？现在区间已经排序成 b1≤b2≤b3…了，考虑 a1 和 a2 的大小关系。

情况 1 ： a1>a2 ，如图（ a ） 所示， 区间 2 包含区间 1 。 前面已经讨论过，这种情况下一定不会选择区间 2 。不仅区间 2 如此，以后所有区间中只要有一个 i 满足 a1>ai， i都不要选。 在今后的讨论中， 将不考虑这些区间。
情况 2 ： 排除了情况 1 ， 一定有 a1≤a2≤a3≤…， 如图（ b ）所示。 如果区间2 和区间 1完全不相交， 那么没有影响（ 因此一定要选区间 11）， 否则区间 1 和区间 2最多只能 选 一个。 如果不选区间 2 ， 黑色部分其实是没有任何影响的（ 它不 会挡住任何一个区间）， 区间 1 的有效部分其实变成了灰色部分， 它被区间 2所 包含！ 由刚才的结论， 区间 2 是不能选的。 依此类推， 不能因为选任何区间而放弃区间 1 ， 因此选择区间 1 是明智的。
选择了区间 1 以后， 需要把所有和区间 1 相交的区间排除在外， 需要记录上一个被选择的区间编号。 这样， 在排序后只需要扫描一次即可完成贪心过程， 得到正确结果。