贪心

贪心应该是一种思想，而不是模版

这里我学习区间模版

多做题应该就积累会了,这里似乎有好几种证明方法
 [https://www.acwing.com/file_system/file/content/whole/index/content/10907534/](http://) 
 夹逼准则，替换法，反证法

区间选点

这种区间问题应该都是先把区间排个序
左端点排序，我们就可以从头开始处理
如果右端点排序，那么我们应该是从尾巴开始处理

这里提及证明思想，最优解ans，我们的解cnt
我们首先写出了一个解，最优解的点数肯定小于等于我们的
ans<=cnt
我们在排序处理后，得到cnt，那么我们可以知道
至少有cnt个互不相交的区间，所以至少要有cnt个点
ans>=cnt
这样证明了我们的解是最优

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
typedef struct{
    int r;
    int l;
}range;

bool cmp(range a,range b){
    return a.l<b.l;
}

int main(){
    int n;
    range data[N];
    cin>>n;
    for(int i=1;i<=n;i++) cin>>data[i].r>>data[i].l;
    sort(data+1,data+n+1,cmp);
    // for(int i=1;i<=n;i++) cout<<data[i].r<<' '<<data[i].l<<endl;
    int minl=-2e9;
    int res=0;
    for(int i=1;i<=n;i++){
        if(minl<data[i].r){
            minl=data[i].l;
            res++;
        } 
    }
    cout<<res;
}

最大不相交区间数量

其实和上道题功能一样，就是换了个说法，我们上一道题作用就是
从若干个区间中，找到了最大不相交区间数

区间分组

这里看到一个等价问题非常好理解
 [https://www.acwing.com/solution/content/8902/](http://)
 看做是教室分配问题，很好记忆和理解

那么我们先按照开始时间将所有活动排序

然后遍历所有活动，如果当前活动可以放在已分配的某个教室里面
我们就把他加入到这个教室里面
如果没有任何一个当前教室可以加入这个活动
那么我们就新开一个教室

判断能不能加入当前教室，就是教室什么时候活动结束，空闲的时候我才能放入
那么这么多个教室，我们选择的是结束时间最早的那个
这里使用堆来

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

using namespace std;

typedef struct{
    int l;
    int r;
}range;

bool cmp(range a,range b){
    return a.l<b.l;
}

int main(){
    int n;
    cin>>n;
    range data[n+1];
    for(int i=1;i<=n;i++) cin>>data[i].l>>data[i].r;
    sort(data+1,data+n+1,cmp);
    // for(int i=1;i<=n;i++) cout<<data[i].l<<' '<<data[i].r<<endl;
    priority_queue<int,vector<int>,greater<int>> heap;//这样就定义了小根堆
    //我感觉less理解为降序，说明大根堆
    //greater理解为升序，说明小根堆
    for(int i=1;i<=n;i++){
        if(heap.empty()||data[i].l<=heap.top()){
            heap.push(data[i].r);
        }
        else{
            heap.pop();
            heap.push(data[i].r);
        }
    }
    cout<<heap.size();
}

合并果子

就是哈夫曼树的实现，这里比课本上简单多了，只需要输出最终的值即可