深圳互联网_免费制作海报的app_营销网站的建造步骤_全国疫情最新消息今天新增

前言

前面两个都是右端点排序，这个我又是无脑右端点排序，直接 wa 了。哭。感觉反正做什么事情都不要太着急，心平气和地做还是比较好。没什么大不了的。考点统计

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct Range{int l,r;bool operator< (const Range&W)const{return l<W.l;}
}range[N];
int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>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++){auto r=range[i];if(heap.empty()||heap.top()>=r.l){heap.push(r.r);}else{heap.pop();heap.push(r.r);}}cout<<heap.size();return 0;
}

思路

想知道小根堆是啥，之前学过语法，但是因为害怕这种不熟悉的东西，基本自己没咋写过，什么结构体，指针，vector ，我都没咋写过。还是不能着急，得自己慢慢把里面的每一个细节想清楚，至少要把自己说服，能自洽。

堆（大根堆、小根堆）：大根堆的堆顶是最大值，小根堆的堆顶是最小值，感觉很正常。嗷嗷，原来这个是 stl 部分的内容，没事，正好补一补这块的知识。

priority_queue<int> q;                              // 大根堆
priority_queue<int, vector<int>, greater<int>> q;   // 小根堆

知道上面的就可以了，其他的我好像知道。

小根堆存的就是组的数目，我们可以查询的就是最小值，假设现在右端点的最小值比新的左端点大，说明什么？说明两个区间有交集，有交集就需要新增一个组，就直接把新的组的右端点加到小根堆里面，假设两个组没有交集，没有交集可以把两个区间放在一个组里面，此时不需要新增组，那我们更新一下最小值就可以了。

这里有点儿绕，也是我之前一直没有想清楚的地方。就是两个区间没有交集，我们不需要新增组，我们把新加的区间的右端点存到小根堆里面。因为我们是按照左端点排序的，只把每个区间的右端点存进了小根堆，这里面的逻辑是啥，还是有点懵。哦哦，我懂了。画了一个示意图，感觉大概懂了，就是不断更新，循环更新确实比较抽象。