AcWing 906. 区间分组
原题链接
简单
作者:
术
,
2021-03-08 13:03:52
,
所有人可见
,
阅读 230
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N=100005;
struct Node{
int l,r;
bool operator< (const Node &b)const{
return l<b.l;
}
}node[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
node[i]={l,r};
}
sort(node,node+n);
priority_queue<int,vector<int>,greater<int>> pq;
int res=0;
for(int i=0;i<n;i++){
if(pq.empty()||node[i].l<=pq.top()){
res++;
pq.push(node[i].r);
}
else if(node[i].l>pq.top())
{
pq.pop();
pq.push(node[i].r);
}
}
cout<<pq.size();
//cout << "Hello world!" << endl;
return 0;
}