AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
Bug-Free
,
2021-05-24 00:07:55
,
所有人可见
,
阅读 437
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
#define x first
#define y second
int n;
vector<pii> interval;
bool cmp(pii a, pii b)
{
return a.y < b.y;
}
int main()
{
cin >> n;
while (n--) {
int l, r;
cin >> l >> r;
interval.push_back({l, r});
}
sort(interval.begin(), interval.end(), cmp);
int ans = 0, ed = -1e9 - 10;
for (auto item : interval) {
if (ed < item.x) {
ans++;
ed = item.y;
}
}
cout << ans << endl;
return 0;
}