AcWing 422. 校门外的树
原题链接
简单
作者:
回头不是从前
,
2021-01-16 16:09:22
,
所有人可见
,
阅读 210
(区间合并 C++: 17ms)
#include<iostream>
#include<algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
PII area[100];
// 区间合并
int main() {
int l, m;
cin >> l >> m;
int res = l + 1;
for(int i = 0; i < m; ++i) cin >> area[i].x >> area[i].y;
sort(area, area + m);
PII cur = area[0];
for(int i = 1; i < m; ++i) {
if(cur.y >= area[i].x) {
if(cur.y < area[i].y) cur.y = area[i].y;
} else {
res -= (cur.y - cur.x + 1);
cur = area[i];
}
}
res -= (cur.y - cur.x + 1); // 最后还要减去一次
cout << res;
return 0;
}