（贪心）区间问题大致思路

1.选择不相交区间。

a.描述：

数轴上有n个开区间(ai, bi)。选择尽量多个区间，使得这些区间两两 没有公共点。

b.思路总结：

1.区间x完全包含y，选y
2.按照bi从小到大排序，从第一个区间开始选
3.把所有和上一个区间相交的区间排除在外

c.思路分析：

首先明确一个问题：假设有两个区间x,y，区间x完全包含y。那么，选x是不划算的，因 为x和y最多只能选一个，选x还不如选y，这样不仅区间数目不会减少，而且给其他区间留出 了更多的位置。接下来，按照bi从小到大的顺序给区间排序。
贪心策略是：一定要选第一个 区间。

现在区间已经排序成b1≤b2≤b3…了，考虑a1和a2的大小关系。

情况1：a1>a2，如图所示，

区间2包含区间1。前面已经讨论过，这种情况下一 定不会选择区间2。不仅区间2如此，以后所有区间中只要有一个i满足a1>ai，i都不要选。在 今后的讨论中，将不考虑这些区间。
情况2：排除了情况1，一定有a1≤a2≤a3≤…，如图所示。

如果区间2和区间1完全 不相交，那么没有影响（因此一定要选区间1），否则区间1和区间2最多只能选一个。如果 不选区间2，区间1的1部分其实是没有任何影响的（它不会挡住任何一个区间），区间1的有效部 分其实变成了2部分，它被区间2所包含！由刚才的结论，区间2是不能选的。依此类推， 不能因为选任何区间而放弃区间1，因此选择区间1是明智的。
选择了区间1以后，需要把所有和区间1相交的区间排除在外，需要记录上一个被选择的 区间编号。这样，在排序后只需要扫描一次即可完成贪心过程，得到正确结果。

2.区间选点问题。

a.描述：

数轴上有n个闭区间[ai, bi]。取尽量少的点，使得每个区间内都至少有 一个点（不同区间内含的点可以是同一个）。

b.思路总结：

1.按b从小到大排序（b相同时a从大到小排序）
2.区间包含的情况 下，大区间不需要考虑。
3.取最后一个点

c.思路分析：

如果区间i内已经有一个点被取到，则称此区间已经被满足。受上一题的启发，下面先 讨论区间包含的情况。由于小区间被满足时大区间一定也被满足，所以在区间包含的情况 下，大区间不需要考虑。
把所有区间按b从小到大排序（b相同时a从大到小排序），则如果出现区间包含的情 况，小区间一定排在前面。第一个区间应该取哪一个点呢？此处的贪心策略是：取最后一个 点，

根据刚才的讨论，所有需要考虑的区间的a也是递增的，可以把它画成图8-8的形式。如 果第一个区间不取最后一个，而是取中间的，如a点，那么把它移动到最后一个点b后，被 满足的区间增加了，而且原先被满足的区间现在一定被满足。不难看出，这样的贪心策略是 正确的。

3.区间覆盖问题。

a.描述：

数轴上有n个闭区间[ai, bi]，选择尽量少的区间覆盖一条指定线段[s,t]。

b.思路总结：

1.每个区间在[s, t] 外的部分都应该预先被切掉
2.按照a从小到大排序，选择起点在s的最长区间[ai，bi]
3.新的起点应 该设置为bi，忽略所有区间在bi之前的部分

c.思路分析：

本题的突破口仍然是区间包含和排序扫描，不过先要进行一次预处理。每个区间在[s, t] 外的部分都应该预先被切掉，因为它们的存在是毫无意义的。预处理后，在相互包含的情况 下，小区间显然不应该考虑。
把各区间按照a从小到大排序。如果区间1的起点不是s，无解（因为其他区间的起点更 大，不可能覆盖到s点），否则选择起点在s的最长区间。选择此区间[ai, bi] 后，新的起点应 该设置为bi，并且忽略所有区间在bi之前的部分，就像预处理一样。虽然贪心策略比上题复 杂，但是仍然只需要一次扫描

s为当前有效起点（此前部分已被覆盖），则 应该选择区间2。