思路
第一步:将区间按左端点排序
第二步:枚举。(可以先将第一个区间建一个组)枚举每一个组,判断当前区间的左端点是否大于某个组的右边界,若有则让该区间加入这个组并更新该组的右边界,若没有则为该区间新建一个组。
其中只要是满足条件的组,都可以加入,可以加入右边界最小的组。那么我们就可以直接判断该区间是否能加入右边界最小的组,若右边界最小的组都加不进去,那就更别说其他组了。每个组的右边界可以直接用小根堆来存,每次取堆顶直接作判断即可。
- 正因为每次要判断当前区间的左端点和某组的右端点(右边界)的关系,所以按照左端点来排序
C++ 代码
- end 存每一个组的右边界,end的长度即总组数
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int n;
PII q[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
q[i] = {l,r};
}
sort(q,q+n); //按左端点排序
priority_queue<int,vector<int>,greater<int>> end; //end用来存每组的右端点
end.push(q[0].second); //至少会有一个组,先把第一个区间右端点加入,从第二个区间开始即可
for(int i=1;i<n;i++)
{
if(q[i].first > end.top()) end.pop(); //可以加到某个组后边,更新这个组的右端点(先pop,再加入更新后的值)
end.push(q[i].second); //不管能不能找到组,都把新的右端点加入
}
cout<<end.size()<<endl;
return 0;
}