区间分组（详细注释）

//算法思想：1.首先按照区间左端点的大小进行排序（只有按照左端点排序之后才能保证后面的操作正确）
//2.利用小根堆：priority_queue<int, vector<int>, greater<int>> heap保存每组区间的右端点，那么
//堆顶元素就是所有组中右端点最小的那一个组，我们在判断新加进来的区间是否需要开一个新的组时，
//只需与堆顶元素作比较就可以了。如果加入区间的左端点小于堆顶元素的值，那么需要开一个新组来存放
//当前加进来的区间（注意：如果有多个区间满足可以添加当前区间的条件，那么当前这个区间加在任何一
//个分组都可以，因为前面我们已经对所有的区间进行左端点排序）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;

const int N=100010;

typedef pair<int ,int> PII;
//用pair类型来存储区间，方便排序

PII num[N];

int main(){

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        num[i].first=a;
        num[i].second=b;
    }

    sort(num,num+n);//对区间按照左端点进行排序
    priority_queue<int,vector<int>,greater<int>> heap;//创建小根堆，背下来！！

    for(int i=0;i<n;i++){
    //如果堆顶的值大于加入区间的左端点，那么产生一个新的组，对应堆的操作就是push当前加入区间的右端点
        if(heap.empty()||heap.top()>=num[i].first){
            heap.push(num[i].second);
        }
        //否则直接加入弹出堆顶（弹出一组的右端点），并更新成新的组的右端点。
        else{
            heap.pop();
            heap.push(num[i].second);
        }
    }

    cout<<heap.size();//最后堆的size就是分组的个数

    return 0;
}