803. 区间合并

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int main() {
    int n;
    cin >> n;
    if (!n) return 0;
    vector<PII> vec(n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        vec[i] = {a, b};
    }
    //排序，保证每个区间的左边界不会小于上一个区间的左边界
    sort(vec.begin(), vec.end());
    int cnt = 1;
    PII pre = vec[0];//保存上一个独立区间
    for (auto i : vec) {
        //判断当前区间左边界是否在上一个区间内部，若在内部则合并，否则当前区间可独立为一个新区间
        if (i.first >= pre.first && i.first <= pre.second) pre.second = max(pre.second, i.second);
        else {
            pre = i, cnt ++;
        }
    }
    cout << cnt << endl;

    return 0;
}