AcWing 803. 区间合并
原题链接
简单
作者:
acdongla
,
2021-03-10 22:09:40
,
所有人可见
,
阅读 223
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
int n;
const int inf = 2e9;
vector<PII> rev;
void merge() {
int st = -inf, ed = -inf;
sort(segs.begin(), segs.end());
for (auto seg : segs) {
if (ed < seg.first) { // 新区间
if (st != -inf) rev.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != -inf) rev.push_back({st, ed});
segs = rev;
}
int main(void) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
merge();
printf("%d", segs.size());
return 0;
}