核心:贪心,这里体现在为了让分组数量小,让每个组里面的区间尽可能的多
1 首先对数组左端点排序
2 枚举每个区间,判断该区间是否加入已存在的组中:
①如果该区间的左端点比存在的所有组中的最小右端点(注意:这里的右端点针对组而言的,指的是一个组里面所有区间中右端点最大值)小
则将该区间放入该组。同时更换这个组的右端点
②否则:我们就新开一个组,放入该区间。
3.这里我们用小根堆来维护,每个组的右端点。堆顶就代表针对组而言,右端点最小的组。
如果是需要添加新的组,直接新组的右端点加入堆中。
堆里面元素的个数就是我们的分组的数量。
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5;
pair <int,int> range[N];
int n;
int main(){
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
range[i]={a,b};
}
sort(range,range+n);
priority_queue<int,vector<int>,greater<int> > heap;
for(int i=0;i<n;i++){
if(heap.empty()||heap.top()>=range[i].first){
heap.push(range[i].second);
}
else{
heap.pop();
heap.push(range[i].second);
}
}
printf("%d",heap.size());
return 0;
}