题目描述
给N个区间,求多少个数轴可以不相交的存放所有区间
思考
这不就是魔改的活动安排吗!
首先我们来回忆一下活动安排:
给N个区间,问一个数轴最多承载几个不相交区间
对于活动安排问题,我们的贪心策略是这样的:
首先把所有区间按照结束点大小排序
然后枚举这个数列,不断更新上一个结束的值,满足即放入
这个算法的核心思想就是,在你满足放入条件的同时,尽量给后者的放入留下更多的空间
但是与本题不同的是,本题不可以舍弃区间,但是本题可以添加数轴
但是对于原来的贪心思路,我们仍然认可,我们只需要做以下调整
如果已经存在多个数轴,那么选择满足条件的结尾最大的那一根
如果没有满足的数轴,就只好自己加入一根数轴了!
但是,我发现,虽然这个思路是对的,但是对于10^4级别的数据规模来说,确实会超时QAQ(O(n^2))
于是,我们只好开始想另一种思路....
我发现,时间被卡的问题主要在于:从前往后寻找最差的数轴放入,放入之后又要维护数轴排序
那么,有没有什么办法可以免去寻找最差数轴和维护完整排序的时间呢?
我们想到,活动安排里面,为什么优先考虑结束时间?
因为对于同样增加一个活动,结束的早,会留出更多时间给后面
但是对于这个题目,每一个活动都必须选入!而且可以开多个数轴!
所以,对于每个数轴中结束最早的那个,如果最早开始的区间不能放进去,那么只有新开数轴了!
如果能放进去呢,也不需要挑差的,因为自己作为最早开始的区间,后面的区间开头都要比你大,如果你能更差的,那他们必然更可以!
所以。我们改了又改的贪心策略最后还是出来了
相比较上一个,我们不需要一个一个挑差的了,也不需要维护完整排序,只需要维护一个堆就可以啦!
qwq我太难了
P.S. 以后写算法之前先算一下复杂度看能不能过
(贪心) $O(nlogn)$
C++ 代码
#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
int n;
struct cow{
int fir,las,num,sam;
}line[60000];
struct lan{
int sto,num;
};
bool cha(cow a,cow b){return a.fir<b.fir;}
bool bac(cow a,cow b){return a.sam<b.sam;}
bool operator <(const lan& a,const lan& b){
return a.sto>b.sto;
}
lan make_lan(int sto,int num){
lan a;
a.sto=sto;
a.num=num;
return a;
}
priority_queue<lan,deque<lan> > cao;
int main(){
cin >> n;
for(int i=0;i<n;i++){ cin >> line[i].fir >>line[i].las; line[i].sam=i;}
sort(line,line+n,cha);
cao.push(make_lan(0,1));
for(int i=0;i<n;i++){
if(line[i].fir> cao.top().sto ){
line[i].num=cao.top().num;
cao.push(make_lan(line[i].las,cao.top().num));
cao.pop();
}else{
line[i].num=cao.size()+1;
cao.push(make_lan(line[i].las,cao.size()+1));
}
}
sort(line,line+n,bac);
cout << cao.size() <<endl;
for(int i=0;i<n;i++){
cout << line[i].num << endl;
}
return 0;
}
6orz