这篇题解内容冗长
还请耐心浏览
首先我们再来熟悉一遍题目:
我们有n个区间a[i]~b[i],我们将这些区间进行一个分组操作,而这种操作只按照一种标准,就是,每一组内部的区间不能
存在交集。
以此标准,让我们求出最小组数。
注意一点,只要组内所有的区间不存在交集就可以算是一个组,详情看下图
所以你看,很神奇吧这道题,别看这有那么多的区间,其实只要按照题目要求来进行操作分组,最后分的组可能不是你想象的那样,如果和你想的不一样,那么,只能说是自己想错了,而不是题目本身错了,建议,多理解理解题目含义,我就是读了好多遍题目,才理解了这道题目,然后才理解了y总视频讲课的内容
下面我们来看看该怎么做这道题目
方案:
步骤1
我们首先要做的一步是排序,让后面的操作更好梳理,这里按左端点排序。(本人也没对这种选法理解通透,如果理解清了,会来更新的。)
个人对区间选点的理解
选择左端点:需要与前面的区间进行比较
选择右端点:需要与后面的区间进行比较
(注:是指在思考问题,确定方案的时候,不是在写代码的时候)
步骤二
我们要做的就是枚举每个区间,看看当前区间是不是和现有的组存在交集。
【或者理解为:我们看看每一个组的最后一个区间是否和当前这个区间是不是有交集。】
由这种判断方式,我们可以进行如下两种操作:
1、如果当前枚举到的这个区间和某一个组没有交集,我们就把他放入这个组内。【即:当前区间左端点大于现在某个组的右端点,
我们将这个区间归为这一组,注意更新组的右端点】
2、如果当前枚举到的这个区间和现有的所有的组都有交集,我们就不能将这个区间归到组内,而是要给他新开一个组。
【即,当前区间的左端点小于或等于现有的所有组的右端点,我们就从新开一个组】
优化:
在步骤二里面处理当前区间的时候,只有两种操作,可以说是两种选择。一个是与某一个区间没有交集(如1),一个是所有的区间都有交集(如2),但是这两种操作在具体实现的时候,都有一些小小的困难,所以,在这里我们来做一些小小的优化。
我们可以这样做:
如果当前区间的左端点比最小的组的右端点都要小,这不就符合2了么,满足与所有的组都有交集的这个条件。如果不满那就属于1了,因为这个是一个二元问题,不是2就是1
这也就解释了为什么要用小根堆这个东东了,我们只要使用当前所有组的最小右端点就可以了呀!!!
下面为君奉上我的代码
#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 ++ ) 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 t = range[i];
if (heap.empty() || heap.top() >= t.l)//如果当前队列为空,或者区间的端点小于小根堆的根(当前组的最小右端点)
heap.push(t.r);//那么这个区间就是一个大佬,和所有组都有仇,自己单开一组
else{
heap.pop();//如果大于组当中的最小右端点,说明它至少肯定和这个组没有交集,没有交集那就把它归到这一组离
heap.push(t.r);//既然大于我们小根堆的根,也就说明把它该归到小根堆根所代表的这一组,根就失去了作用
}//我们将跟去掉,用新的t.r来放入小根堆里,小根堆替我们自动找到所有组当中为所有组的最小右端点,并作为新根
}
cout << heap.size() << endl;//我们就是用size来表示的组的
return 0;
}
###tql
醍醐灌顶
同学,您好,请教您一下,这个最小组是按照什么判断的呢,怎么判断哪个组是最小组呢
相当于找到一个右端点最小的组,如果需要加入的区间的左端点大于这个最小右端点,这个区间就可以被划进去
为什么开新组和合并组都是heap.push
因为答案就是heap的长度
是不是有点问题呀,堆中存的是不是应该是 每一组的最大右端点,也就是当前组的最大右端点,注释有点问题
没问题 ,堆是小根堆,y总也是这么讲的
这段话是什么意思啊,可以解释一下嘛?这个题目为什么是左端点排序?
个人对区间选点的理解
选择左端点:需要与前面的区间进行比较
选择右端点:需要与后面的区间进行比较
(注:是指在思考问题,确定方案的时候,不是在写代码的时候
嗯。。。选择按照左端点进行排序,为什么就需要和之前的区间进行比较呢》
清晰,一下就明白了
可以说是讲得最清楚的一篇题解了,赞
为什么不能右端点排序
赞!清晰明了,配合y总视频绝了
hhh~