关于区间贪心的补全

风和日丽 2019-06-30

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

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

一、区间不相交

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

关于区间贪心的补全
当出现这钟情况的时候,我们应该优先选择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即可

相关推荐