AcWing 803. 区间合并
原题链接
简单
作者:
发光二极管
,
2020-02-08 16:11:24
,
所有人可见
,
阅读 481
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
PII arr[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> arr[i].first >> arr[i].second;
sort(arr, arr + n);
int end = arr[0].second; // 记录上个区间的末尾端点
int res = 0; // 记录答案
for (int i = 1; i < n; ++i)
{
if (arr[i].first > end || i == n - 1) // 如果当前点左端点大于前面区间中最右边的端点,说明两者没有重合
{
++res;
end = arr[i].second;
}
else end = max(end, arr[i].second);
}
cout << res << endl;
return 0;
}