AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
dancin
,
2024-11-27 21:29:25
,
所有人可见
,
阅读 1
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5+10;
typedef pair<int,int> PII;
PII a[N];
bool compare(const PII&a,const PII&b)
{
return a.first<b.first;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(int i = 0;i<n;i++) cin >> a[i].first >> a[i].second;
sort(a,a+n,compare);
int cnt = 1;
int ed = a[0].second;
for(int i = 1;i<n;i++)
{
if(ed>=a[i].first) ed =min(ed,a[i].second);
else
{
cnt++;
ed = a[i].second;
}
}
cout << cnt << endl;
return 0;
}