AcWing 906. 区间分组
原题链接
简单
作者:
minux
,
2020-05-04 17:08:17
,
所有人可见
,
阅读 509
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Range{
int l, r;
bool operator<(const Range &o) const{
return l<o.l;
}
}range[N];
int n;
int main(){
// 贪心策略:找到一个尽可能容纳最多区间的组
cin>>n;
int a, b;
for(int i=0; i<n; ++i){
cin>>a>>b;
range[i]={a, b};
}
sort(range, range+n); // 将区间按照左端点从小到大进行排序
// 使用小根堆维护区间组的右端点
priority_queue<int, vector<int>, greater<int>> pq;
for(int i=0; i<n; ++i){
Range R = range[i];
if(pq.empty() || pq.top()>=R.l) pq.push(R.r); // 区间不可兼容, 新开分组
else{
// 区间可兼容, 更新组信息, 将组的右端点设置为新加入的区间右端点
pq.pop();
pq.push(R.r);
}
}
cout<<pq.size()<<endl;
return 0;
}