python/TangDou/AcWing/MergeInterval/803.cpp

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
vector<PII> res;

void merge() {
    if (!segs.size()) return; // 本题中没有实际意义，为了防止下面segs[0]越界

    // ① 按左端点排序
    sort(segs.begin(), segs.end());
    int st = segs[0].first, ed = segs[0].second;     // 第一只猴子默认为大王
    for (int i = 1; i < segs.size(); i++)            // 后续的猴子开始枚举
        if (ed < segs[i].first) {                    // ② 无交集
            res.push_back({st, ed});                 // 发现新大陆
            st = segs[i].first, ed = segs[i].second; // 重新设置起始、终止值
        } else                                       // ③ 有交集
            ed = max(ed, segs[i].second);            // PK最大值

    // ③ 残余势力入数组
    res.push_back({st, ed});
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge();
    printf("%d\n", res.size());
    return 0;
}