算法1
思路:利用区间合并模板
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1000010;
typedef pair<int,int> PII;//每个区间是有两个端点,所以我们用pair存储
int n;//n个区间
vector<PII> segs;
//区间合并模板
void merge(vector <PII>&segs){
vector<PII> res;//合并之后结果
sort(segs.begin(),segs.end());//先把所有区间排序
int st=-2e9,ed=-2e9;
for(auto seg:segs){//区间从头到尾遍历
if(ed<seg.first){
if(st!=-2e9)res.push_back({st,ed});//没有交集,直接push
st=seg.first,ed=seg.second;//否则处理左右端点
}
else ed=max(ed,seg.second);
}
if(st!=-2e9) res.push_back({st,ed});//处理空集
segs=res;
}
int main(){
cin>>n;
//读入区间的每个端点
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
cout<<segs.size()<<endl;
return 0;
}