题意理解

给区间分组，要求分组内部没有交集 互不冲突，可以分几个

思路

• 按照左端点排序

• 从前到后枚举区间，判断当前区间能否加入现有分组中的某个分组中去，还是要另立门户

  • 在当前分组中，若存在这么一个分组，使得当前区间的左端点比其右端点小，说明有交集，改区间就要自立门户
  • 如不存在这么一个分组，说明当前区间是可以加入到某个现有分组中去

数据结构优化

快速判断是否存在那个分组，而不用全部遍历判断

为了方便的判断,在当前分组中，是否存在这么一个分组，使得当前区间的左端点比其右端点小,只要比较左端点是不是比最小的右端点还要小即可

这样就用到最小堆这个数据结构，来帮我们减少当前区间的左端点和每个分组区间的右端点比较的次数。
只需要和最小的右端点比较即可

收获

• 小根堆

复杂度分析

时间复杂度 ： $o(nlogn)$

c++代码

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

using namespace std;

typedef pair <int, int>  PII;

const int N = 100010;

int n;
vector<PII> segs;

int desperate(vector<PII> &segs)
{
    int res = 0;
    sort(segs.begin(), segs.end());

    priority_queue<int, vector<int>,greater<int>> heap;

    for(auto seg : segs)
    {
        // 当前区间的左端点 小于某个分组区间的的右端点   自立门户
        if(heap.empty() || heap.top() >= seg.first) heap.push(seg.second); 
       // 可以加入
        else
        {
            heap.pop(); 
            heap.push(seg.second);
        }

    }

    return heap.size();
}

int main()
{
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        int l ,r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    cout << desperate(segs) << endl;

    return 0;

}