之前在博客里总结过贪心算法的相关注意概念，但是由于当时理解不够，并没有很好的总结区间贪心问题，所以在这里做一个总结：

区间贪心算法总的来说有两大题型，一个是区间不相交问题，一个是区间选点问题；

其实第二种问题是第一种问题的子问题，并且对于贪心算法中的概念一定要有所体会；

一、区间不相交

区间不相交问题就是对给定的一些开区间中，尽可能多的选择开区间，使得这些开区间两两没有交集；

对于这个问题，首先要理解重叠区间的概念，也就是对于下列图片所给的情况：

当出现这钟情况的时候，我们应该优先选择I1，因为这样的话就可以给其他区间腾出很多的空闲位置；其次，当消除了所有子区间重叠问题的时候，我们会有如下的情况出现：

对于这种情况，我们采用的是对各个区间按照左端点的大小进行排序，此时就会形成上图的情况，每个区间的有右边节点有序；

代码如下所示:

#include
    
     #include
     
      #include
      
       using namespace std;const int maxn=110;struct Inteval{    int x,y;}I[maxn];bool cmp(Inteval a,Inteval b){    if(a.x!=b.x)        return a.x>b.x;//左端从大到小进行排序    else        return a.y
      
     
    

其实最难理解的应该是代码中的处理，这里给出详细的解释：

首先来看排序函数

bool cmp(Inteval a,Inteval b){    if(a.x!=b.x)        return a.x>b.x;//左端从大到小进行排序    else        return a.y

这里之所以要在左端大小相同的情况下对右端进行递增排序，是为了找出包含区间中的最小的子区间；

这样进行排序的时候，就会变成存在包含关系的区间在一起，但是首位肯定是包含区间中的最小区间；

之后就是主体处理；

while(scanf("%d",&n),n!=0){        for(int i=0;i

这里注意for循环，其实就是对数组进行上述分析的第二部处理，从右向左，寻找不重合的区间（由于排序函数的操作，找到的必定是重合区间中的最小区间），循环从而使得每次选择出来的都是最小的不重合的区间；

个人认为，区间不重叠的贪心思路主要体现在寻找最小的包含区间上；对于每一块有重合情况的区间，我们只需要找出每一块的重合区间中的最小区间，就可以组合成不重叠的区间，并且这些区间肯定数目最大，符合题意；

二、区间选点

区间选点可以视为第一种问题的衍生问题，目的是将给出开区间（注意，这里是开区间）中选择点，使得每个区间都至少有一个点；该问题也涉及重叠区间的问题。

还是一样，当上述情况发生的时候，我们如果点放在I1内，就会使得I2内也存在点；所以根本上来说，我们还是寻找重叠区间内最小的区间；因此，我们采用的还是第一类问题的操作，但是需要注意的就是点的选取；对于有序的序列，我们应该把点选在左端点，而不是右端点；

关于这个问题，可以这样想:

对于上述情况，如果选取右端点，就会出现选择两个的情况，但是如果选取左端点，就只用选取一个；

所以，只需要对之前的代码进行修改，修改一个判定条件；将I[i].y<=lastX修改为I[i]<lastX即可