C++

$\color{#cc33ff}{— > 算法基础课题解}$

思路：

区间合并

$模板题$

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> PII;
int n;
vector<PII> segs;

void merge(vector<PII> &segs){
    vector<PII> res; // 存储合并之后的结果

    sort(segs.begin(), segs.end()); //pair在C++里面排序会优先以左端点排序，再以右端点排序
    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(){
    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;
}