区间合并

AcWing-803-区间合并

实现

#include <iostream>
#include <vector>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;

typedef pair<int, int> PII;
int n;
vector<PII> itv, res;

void merge () {
    int beg = -inf, end = -inf;
    for (int i = 0; i < itv.size(); ++ i) {
        int l = itv[i].first, r = itv[i].second;
        if (end < l) {
            if (beg != -inf) res.push_back({ beg, end });
            beg = l, end = r;
        } else {
            end = max(end, r);
        }
    }
    if (beg != -inf) res.push_back({ beg, end });
}

int main () {
    cin >> n;
    for (int i = 1, l, r; i <= n; ++ i) {
        cin >> l >> r;
        itv.push_back({ l, r });
    }

    sort(itv.begin(), itv.end());
    merge();
    cout << res.size() << endl;
    return 0;
}