算法分析
贪心决策
从前往后枚举每个区间,判断此区间能否将其放到现有的组中
-
如果一个区间的左端点比最小组的右端点要小,
ranges[i].l<=heap.top()
, 就开一个新组heap.push(range[i].r);
-
如果一个区间的左端点比最小组的右端点要大,则放在该组,
heap.pop(), heap.push(range[i].r);
每组去除右端点最小的区间,只保留一个右端点较大的区间,这样
heap
有多少区间,就有多少组。
算法流程
区间分组,在组内区间不相交的前提下,分成尽可能少的组。
而不是尽可能多的组,因为一个区间一组,就是尽可能多组的答案。
等效于把尽可能多的区间塞进同一组,要满足range[i].l > heap.top
。
heap
存储的是每个组的最右的端点,由于是小根堆heap.top()
是对应的最小的最右点。
那如果遇到,塞不进去的情况呢?
就是heap.top >= range[i].l
, 当前区间的左端点比最小的右端点还要小,放到任何一组都会有相交部分。
那就需要新开一组,heap.push(range[i].r)
.
-
把所有区间按照左端点从小到大排序
-
从前往后枚举每个区间,判断此区间能否将其放到现有的组中
-
heap
有多少区间,就有多少组
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
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 ++ )
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, 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;
}
区间当成一个人占用某物品的时间,谁先来(左端点小)谁先上,哪个物品先用完(右端点小)先腾出来哪个。
wc,厉害
懂了 感谢
祝阁下cf上紫
__,救困扶危韩老魔感谢楼主的解析,我也理解了区间分组的思路!
我的理解是这样的:将每个区间的左端点看做开始位,右端点看做结束位。a.先将所有待比较区间,按照开始位
l
从小到大排序(表示紧急程度,开始位越小,表示越着急需要空间);b.而后开辟优先队列,来登记每个组的结束位r
(表示什么时候能用完),通过对结束位从小到大的方式排序(结束位最小表示:最快能用完,腾出空间给别人);c.最后,待比较区间按紧急程度,依次向优先队列里最早能腾出空间的问:你好了没?如果没好,优先队列会再给它开一个空间,并登记结束时间;如果好了,当前区间就接管(pop最早腾出空间的区间,然后登记接管区间它要多久结束)同学,您好,请教您一下,请问楼主题解中的最小组这个怎么理解,是以什么来比较来确定哪个组是最小组呢
起初的从小到大排序,就保证了先入优先队列的是最小的
greater[HTML_REMOVED] 保证的是 heap 数组是升序的(heap 的底层其实就是一个数组,可以参考模拟堆那个题目)(具有动态排序的性质),因为数组是升序的,所以 heap.top() 的值是最小的,heap 里面的元素表示的是活动结束的时间。
有个问题 就是 假设我最开始对右端点进行排序 按照最大不相交区间进行, 从头到尾进行遍历,每找到一个不相交区间就把它从vector中删除,每进行一次for循环就cnt++ , 当vector个数为空时, 就说明vector里边没有元素了, 但是wa了。。。。
你确定是wa?不是时间超时? 数据是10^5 这么写会超时的
对啊为什么右端点排序会WA啊啊啊
为什么没有人问怎么保证heap里面堆顶不会被更新两次range[i].r呢?也就是说堆顶原本只有一个区间在里面,但是后续又有连续两个区间使得这三个区间都是两两不想交的情况,那么堆顶就会被放入三个区间了呀?可是题目只要求一个组只能放两个区间,这是如何保证的呢?
嗯,重新看了下题目,只是让我们保证一个组内的区间是两两不相交而已,并没有要求我们一个组只能放两个区间,属于是审题不认真了,我也不怕大家笑,这个评论就留在这,以防后面有跟我一样疑问的兄弟拜拜浪费时间。
//用小根堆来存,每次判断我新要入队列的这个区间的左端点比我队首的区间的右端点有没有重合
// 有重合就入队,如果没有重合,是不是他们就可以在一个组里面了,那我是不是可以把队头的元素出队
// 最后剩余在队列中的元素是不是都是不在一组的元素哈
// 他们的个数是不是也就是分组的个数,而且是最小个数
嗯。。。为什么是按照左端点排序呢?
因为左端点越小的越容易跟其他线段重叠,从不能找到可能的过程中,能够贪心的找到一个最小的可能性
为什么要用小根堆啊
heap.pop();
heap.push(range[i].r);
对于这两行代码,我的理解是:
//如果当前遍历到的区间的左端点大于堆顶元素的右端点时,说明两者可以存在于一个区间内
//此时注意要先把堆顶pop出去再将当前区间的右端点push进来
//是因为堆中元素存的是每个组的最大右端点,堆顶是这些最大右端点的最小值
//对于以后新的区间来说,只要他的左端点和某一个组的最大右端点冲突,那么就必须新开一个组
//因此堆中每个元素存的是每个组的最大右端点
以左端点开始排序,方便进行遍历;用小跟堆把满足条件组别的最小区间选出来,如果最小区间的右端点小于遍历区间的左端点,则满足条件,更新最小区间右端点;如果最小区间右端点大于遍历区间左端点,则代表两区间相交,不满足条件;把该区间右端点压入小跟堆,然后小跟堆自动把最小区间右端点排到top,继续遍历比较。
bool operator< (const Range &W)const
{
return l < W.l;
}这个重载小于号是啥意思呀,一会r,一会l的
用于sort()对range的左端点进行排序
为什么不能右端点排序呜呜呜
精辟简介易懂
懂了感谢
nb
思路很好
if (heap.empty() || heap.top() >= range[i].l)为什么条件倒过来这样就不行了呢
要先判断堆是否为空吧,堆不为空才能从里面取元素
heap的两个>放在一起没问题吗??
新版编译器可以的
可以按照右端点递增排序,只不过要从后往前遍历
为什么一定要从左端点排序,如果右端点排序就错了。
0 6
1 4
5 12
8 10
你画图看看这个你就懂了