风和日丽 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
即可