python/TangDou/AcWing/Section/906_yxc.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
struct Node {
    int l, r;
    const bool operator<(const Node &b) const {
        return l < b.l; // 按照左端点进行排序
    }
} range[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

    sort(range, range + n);

    priority_queue<int, vector<int>, greater<int>> heap; // 我们的小根堆始终保证所有组中的最小的右端点为根节点
    // 用堆来存储组的右端点

    for (int i = 0; i < n; i++) {
        auto t = range[i];

        if (heap.empty() || heap.top() >= t.l) // 如果当前队列为空，或者区间的端点小于小根堆的根（当前组的最小右端点）
            heap.push(t.r);                    // 那么这个区间就是一个大佬，和所有组都有仇，自己单开一组
        else {
            heap.pop();     // 如果大于组当中的最小右端点，说明它至少肯定和这个组没有交集，没有交集那就把它归到这一组里
            heap.push(t.r); // 既然大于我们小根堆的根，也就说明把它该归到小根堆根所代表的这一组，根就失去了作用
        }                   // 我们将根去掉，用新的t.r来放入小根堆里，小根堆替我们自动找到所有组当中为所有组的最小右端点，并作为新根
    }

    cout << heap.size() << endl; // 我们就是用size来表示的组的
    return 0;
}