区间合并

发布于 2022-08-01  6 次阅读


#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n;
vector<pair<int, int> > a, b;

void merge() {
    sort(a.begin(), a.end());
    int st = -INF, ed = -INF;
    for (auto item: a) {
        if (ed < item.first) {
            if (st != -INF)b.push_back({st, ed});
            st = item.first, ed = item.second;
        } else ed = max(ed, item.second);
    }
    if (st != -INF) b.push_back({st, ed});
    return;
}

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        a.push_back({l, r});
    }
    merge();
    printf("%d\n", b.size());
    return 0;
}