AcWing 422. 校门外的树
原题链接
简单
作者:
acw_yxy
,
2021-01-20 19:09:17
,
所有人可见
,
阅读 282
区间合并
(区间合并) $O(nlogn)$
nlogn
C++ 代码
// 区间合并到一起后减
#include <iostream>
#include <algorithm>
using namespace std;
vector<pair<int, int>> v;
int main()
{
int m, n;
cin >> m >> n;
m ++;
while(n --)
{
int a, b;
cin >> a >> b;
v.push_back({a, b});
}
sort(v.begin(), v.end());
int start = v[0].first, end = v[0].second;
for(int i = 1; i < v.size(); i ++)
{
if(v[i].first > end) m = m - end + start - 1, start = v[i].first, end = v[i].second;
else end = max(end, v[i].second);
if(i == v.size() - 1) cout << m - end + start - 1;
}
return 0;
}