关于区间贪心的补全

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

区间贪心算法总的来说有两大题型，一个是区间不相交问题，一个是区间选点问题；
其实第二种问题是第一种问题的子问题，并且对于贪心算法中的概念一定要有所体会；

一、区间不相交

区间不相交问题就是对给定的一些开区间中，尽可能多的选择开区间，使得这些开区间两两没有交集；
对于这个问题，首先要理解重叠区间的概念，也就是对于下列图片所给的情况：

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

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

代码如下所示:

#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
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<b.y;//有段从小到大进行排序
}
int main(){
    int n;
    while(scanf("%d",&n),n!=0){
        for(int i=0;i<n;i++){
            scanf("%d%d",&I[i].x,&I[i].y);
        }
        sort(I,I+n,cmp);
        int ans=1,lastX=I[0].x;
        for(int i=1;i<n;i++){
            if(I[i].y<=lastX){
                //该情况下为不相交区间
                lastX=I[i].x;
                ans++;
            }
        }
    }
    system("pause");
}

其实最难理解的应该是代码中的处理，这里给出详细的解释：
首先来看排序函数

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

这里之所以要在左端大小相同的情况下对右端进行递增排序，是为了找出包含区间中的最小的子区间；
这样进行排序的时候，就会变成存在包含关系的区间在一起，但是首位肯定是包含区间中的最小区间；

之后就是主体处理；

while(scanf("%d",&n),n!=0){
        for(int i=0;i<n;i++){
            scanf("%d%d",&I[i].x,&I[i].y);
        }
        sort(I,I+n,cmp);
        int ans=1,lastX=I[0].x;
        for(int i=1;i<n;i++){
            if(I[i].y<=lastX){
                //该情况下为不相交区间
                lastX=I[i].x;
                ans++;
            }
        }
    }

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

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

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

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

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

对于上述情况，如果选取右端点，就会出现选择两个的情况，但是如果选取左端点，就只用选取一个；
所以，只需要对之前的代码进行修改，修改一个判定条件；
将I[i].y<=lastX修改为I[i]<lastX即可