Acwing908 区间分组
贪心
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n;
struct Range{
int l,r;
bool operator<(Range& w){
return l<w.l;
}
}range[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>range[i].l>>range[i].r;
}
sort(range+1,range+n+1);
priority_queue<int,vector<int>,greater<int>> q;
for(int i=1;i<=n;i++){
auto w = range[i];
if(q.empty() || q.top()>=w.l) q.push(w.r);
else{
q.pop();
q.push(w.r);
}
}
cout<<q.size()<<endl;
return 0;
}
阿里巴巴公司氛围 651人发布
查看17道真题和解析
