排序左端点
类比 题目
803. 区间合并
先举个例子
在这种情况下如果继续按照 803. 区间合并 的思想,
动态取r=max(r,q[i].second) ,会发现答案不正确…
再想一下会发现::
如果下一个区间也不再重新选点的话,必须与上一个选点区域有交集,(即上面几个区间的交集,并非并集)所以现在就可以想到取 r=min(r,q[i].second)
至此便已迎刃而解!!!
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> > q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
q.push_back({l,r});
}
sort(q.begin(),q.end());
int l,r=-2e9,ans=0;
for(int i=0;i<n;i++){
l=q[i].first;
if(l>r) {
ans++;
r=q[i].second;
}
else r=min(r,q[i].second);
}
cout<<ans;
return 0;
}