题目思路
题意简单来说就是:两区间有重合就不能是一组,没有重合的两个区间可以归为一组。
首先,将所有区间按照左端点进行升序排序,我们定义一个小根堆用来存放每一组的右端点的值,当区间的左端点值小于等于根节点的时,开辟新的组并存入右端点。否则就可以加入这一堆。
为什么是小根堆? 首先所有区间是按照左端点升序,如果你的左端点值小于右端点值最小的组,这说明你与任意一组都有重合的部分,此时只能新开一组,相反就并入右端点值最小的那一组,为了方便拿到右端点值最小的那一组的右端点采用小根堆。
样例
1 3
5 7
6 9
10 12
2
首先,[1,3]为第一组,右端点3放进堆中。[5,7]与[1,3]没有重合,合为一组,更新第一组的右端点值为7,小根堆根节点为7。[6,9],左端点6<7,有重合所以自成一组,堆中添加一节点记录这一组的右端点值。[10,12]看似可以和[6,9]合为一组,但我们是与右端点值最小的一组进行比较,发现10>7,所以[10,12]应与第一组和为一组,更新第一组的右端点值为12.此时堆中值为9和12正对应了所分为两组的右端点值。
第一次写请多多指教hh
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
struct Range{
int l,r;
bool operator <(const Range& W)const{
return l<W.l;
}
}range[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
range[i]={l,r};
}
sort(range,range+n);
priority_queue<int,vector<int>,greater<int>> heap; //存放每一组的右端点值
for(int i=0;i<n;i++){ //如果左端点小于了右端点值最小的那一组 说明我与每一组都重叠 每一组都容不下我 需要重开一组
if(heap.empty()||range[i].l<=heap.top()){ //区间重叠开新组
heap.push(range[i].r);
}
else { //和右端点值最小的一组并为一组
heap.pop(); //更新右端点
heap.push(range[i].r);
}
}
cout<<heap.size();
return 0;
}