思路
此题先将区间按左端点从小到大排序,再记录已经计算过的区间中最右端的位置,判断每个区间可否合并
注意:要记录前面区间最右端而不是上一个区间的右端,下图是一个生动的例子
蓝色虚线就是最右端,绿点在此线的左侧,是可以合并的,如果只记录上一个的,就无法合并了
代码
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int l,r;
} a[100005];//用结构体存储区间,方便排序
bool cmp(node x,node y){
return x.l==y.l?x.r<y.r:x.l<y.l;
}//以左端点为第一关键字,从小到大排序
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
int lst=a[1].r,cnt=1;
//lst记录已经计算过的区间中最右端达到了哪里,cnt记录有几个区间
for(int i=2;i<=n;i++){
if(a[i].l<=lst) lst=max(lst,a[i].r);//左端点在之前的某个区间里,此区间可合并,更新lst
else cnt++,lst=a[i].r;//左端点不在任何一个区间中,单独开一个新的区间
}
printf("%d\n",cnt);
return 0;
}