区间分组

思路分析

$(1)$ 按区间左端点升序排序
$(2)$ 从左向右遍历每一个区间，判断当前区间能否放到某一个现成的组里。看当前区间左端点和组的最大右端点比较。大于无冲突则可以放，就放进去。不可以，就开一个新组

因为我们对于每一个组只关心它里面的区间右端点最大值，所以我们用一个组的右区间最大值代表一个组

每次将一个区间放到一个组的时候，我们可以放到任何可以放的区间，因为无论如何这个区间放不下去的组（最大右端点的最小值都匹配不了），下一个区间是更不能利用的（左端点更大）

所以出于简单，减少分类标准，我们每次放到右端点最小的组里面，这时候就可以利用小根堆存储组的右端点最大值。最后堆内元素个数就是组的个数

证明

这里因为每次确定冲突是拿区间左端点和组内最大右端点比较，如果这个左端点可以放就放，不能放就不行。因为是按左端点升序排列，当前区间如果不能放进去，上一个区间是更不会放进去的

在放入组内的情况下，左端点越小，越不利，越容易冲突，具有单调性，所以可以按顺序枚举

答案为$ans$，该算法得出的是$cnt$

证明 $cnt$ $>=$ $ans$

这样很明显可以将所有的区间进行分组，所以它是一组划分方式

证明 $ans$ $>=$ $cnt$

首先，我们再添加新的一组时候，那一组的第一个区间是和之前所有区间都有矛盾的

我们假设可以删去一个区间，那么我们可以发现这里面有一个元素（与最后一组第一个元素冲突的，如果是删除最后一组就是最后一组第一个元素），和其他组都不能兼容。出现矛盾，假设不成立。

所以无法删去，得证$cnt$ $<=$ $ans$

综上所述，我们求得的是正确答案

证明

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

using namespace std;

const int N = 100010;

int n;
struct Range // 存区间
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &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 // 反之，把这个区间放到最小组
        {
            heap.pop();
            heap.push(r.r); // 更新最小组的右端点最大值
        }
    }

    printf("%d\n", heap.size());

    return 0;
}