共计 1724 个字符，预计需要花费 5 分钟才能阅读完成。
之前在博客里总结过贪心算法的相关注意概念，但是由于当时理解不够，并没有很好的总结区间贪心问题，所以在这里做一个总结：
区间贪心算法总的来说有两大题型，一个是区间不相交问题，一个是区间选点问题；其实第二种问题是第一种问题的子问题，并且对于贪心算法中的概念一定要有所体会；
一、区间不相交
区间不相交问题就是对给定的一些开区间中，尽可能多的选择开区间，使得这些开区间两两没有交集；对于这个问题，首先要理解重叠区间的概念，也就是对于下列图片所给的情况：
当出现这钟情况的时候，我们应该优先选择 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 即可
