AcWing 803. 区间合并
原题链接
简单
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = int(1e5 + 1);
const int Mod = 998244353;
vector<pair<int, int>> segs;
void merge(vector<pair<int, int>> & segs) {
vector<pair<int, int>> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs) {
if (ed < seg.first) {
if (st != -2e9) res.push_back({ st, ed });
st = seg.first;
ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != -2e9) res.push_back({ st, ed });
segs = res;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
segs.push_back({ l, r });
}
merge(segs);
cout << segs.size();
return 0;
}