Acwing 906. 区间分组

1、将所有区间按照左端点从小到大排序

2、从前往后处理每个区间

        判断能否将其放到某个现有的组中 L[i] > Max_r

        （1）如果不存在这样的组，则开新组，然后将其放进去；

        （2）如果存在这样的组，将其放进去，并更新当前组的Max_r

#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)
    {
        scanf("%d %d", &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)
    {
        if (heap.empty() || heap.top() >= range[i].l) heap.push(range[i].r);
        
        else
        {
            heap.pop();
            heap.push(range[i].r);
        }
    }
    
    printf("%d\n", heap.size());
    
    return 0;
}