C++

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

思路：

贪心

$分析：$

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Range {
    int l, r;
    bool operator< (const Range & w) const {
        return l < w.l;
    }
}range[N];

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

    sort (range, range + n);

    priority_queue<int,  vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++) {
        auto r = range[i];
        if(heap.empty() || heap.top() >= r.l) heap.push(r.r); 
        /* 
            如果堆为空 或者 当前区间的左端点小于等于堆顶（所有分组的最大右端点的最小值）
            则需要开新组
        */
        else {
            int t = heap.top();
            heap.pop();
            heap.push(r.r);
        }
        /*
            没有新开一个组,而是把当前区间放到原来组里面,并且更新最右边的端点值
        */
    }

    cout << heap.size();

    return 0;
}