贪心 区间覆盖问题
一、区间完全覆盖问题
问题描述：给定一个长度为m的区间，再给出n条线段的起点和终点[ai,bi]（闭区间），求最少使用多少条线段可以将整个区间完全覆盖。
样例：一个长度为8的区间，可选的线段有[2,6]，[1,4]，[3,6]，[3,7]，[6,8]，[2,4]，[3,5]。
解题思路：需要最少的线段进行覆盖，那么选取的线段必然要尽量长，而已经覆盖到的区域之前的地方已经无所谓了（可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方），那么真正能够使得线段更成的是右端点，左端点没有太大的意义，所以选择右端点来覆盖
解题过程：
1.将每一个区间按照左端点递增顺序排列，如果左端点相同，按右端点递增顺序排列，如样例，排完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]。
2.设置两个变量 last 和 far
last表示当前已经覆盖到的区域的最右边距离。
far表示在剩下的线段中找到的所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，不断更新，最右边的距离。
3.重复以上过程，直到区间全部覆盖，否则，区间不能全部覆盖。
二、最大不相交区间数问题
问题描述：数轴上有n个闭区间[ai,bi]，要求选择尽量多个区间，使得这些区间两两没有公共点。
样例：数轴上有7个区间，可选的区间有[2,6]，[1,4]，[3,6]，[3,7]，[6,8]，[2,4]，[3,5]。
解题思路：因为需要尽量多的独立的线段，所以每个线段都尽可能的小，对于同一右端点，左端点越大，线段长度越小，所以先将每一个区间按照右端点递增顺序排列，如果右端点相同，按左端点递增顺序排列。
解题过程：
1.依照上述排序，如样例，排完序后为[1,4]，[2,4]，[3,5]，[2,6]，[3,6]，[3,7]，[6,8]。
2.第一次选择[2,4]，接下来只能选择[6,8]，即当前数轴上最多只能选择两个不相交的区间。
三、区间选点问题
问题描述：数轴上有n个闭区间 [ai,bi]，要求选取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
解题思路：为了选择最少的点使得每个区间内至少含有一个点，考虑按区间左端点递增顺序排序，如果左端点相同，则按区间右端点递增顺序排序，然后以第一个区间右端点作为第一个点能覆盖的最大范围。
①当b1>b2时，显然此时一个点能覆盖最大的区域右边界变为b2，同理，以后只要满足 b1>bi，一个点能覆盖的区域右边界就会变为 bi。
②当b1<a2时，显然一个点不能覆盖到区间2上，所以需新开一个点，此时能覆盖的区域最右边界变为b2，同理，以后只要满足 b1<ai，则都要新开一个点，并且其能覆盖的区域右边界将变为 bi。
③ 当b1<b2时，显然区间1和区间2有公共的部分，但此时一个点能覆盖的区域最右边界还是为 b1，无需更新区域最右边界，同理，对于以后只要满足 b1<bi，都无需新开一个点，也无需更新能覆盖区域的最右边界，显然这也是正确的。综上，按区间左端点递增的顺序排序，再按规则贪心选点。
解题过程：
1.按左端点递增顺序排序，如果左端点相同，按右端点递增顺序排序。
2.①从第一个区间右端点开始贪心往后找，如果下一个区间的左端点大于当前已选区间的右端点，说明要新开一个点，计数器加1，同时更新右区间能覆盖的最远距离；②如果下一个区间右端点小于当前已选区间的右端点，说明共享的线段范围缩短了，那么就更新区间右端点为下一个区间右端点，重复以上操作，直至筛选完所有区间。