AcWing 908. 最大不相交区间数量--贪心-->按左端点排序的方法
原题链接
简单
作者:
YMYS
,
2025-04-05 21:50:42
· 河南
,
所有人可见
,
阅读 9
using namespace std;
const int N = 1e5 +10;
struct node{
int l,r;
bool operator< (const node & a){
return a.l > l;
}
}nd[N];
int n;
signed main()
{
freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin >> nd[i].l >> nd[i].r;
}
sort(nd, nd+n);
int r = -2e9;
int ans = 0;
for(int i=0;i<n;i++){
if(nd[i].l > r){
r = nd[i].r;
ans++;
}else{
r = min(r, nd[i].r);
}
}
cout<<ans<<endl;
return 0;
}