算法1介绍
建立一个队列存max(右端点) 升序排列
按照右端点排序 每次遍历一个区间 在队列中二分查找 比该区间的左端点小的最大的右端点
(次低者) 然后更新这个组的max(右端点) 若找不到的话 则新开一组
时间复杂度
O(nlog2n)
但是不知道为什么还是会超时
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<utility>
#include<map>
int dot[100100],len;
bool cmp(pair<int,int> x,pair<int,int> y){
return x.second<y.second;
}
/*
start:查找范围的第一个元素下标
end:查找范围的最后一个元素下标
target:查找的目标值
return:返回<=target的最大值在a[]中的下标,有可能超出下标范围(下溢)
*/
int erfen(int a[],int start,int end,int target){
if(start>=end) return -2;//-2表示错误
int low=start,high=end,mid;
while(low<=high){
mid=(low+high)/2;
if(target>a[mid]) low=mid+1;
if(target<=a[mid]) high=mid-1;
}
return high;
}
int main(void){
int N,fore,rear,i;
cin>>N;
int dot[N+1];
vector<pair<int,int>> v;
while(N--){
cin>>fore>>rear;
v.emplace_back(make_pair(fore,rear));
}
sort(v.begin(),v.end(),cmp);
dot[0]=-0x3f3f3f3f;
int high;
for(auto x:v){
high=erfen(dot,0,len,x.first);
if(high>=0) dot[high]=x.second,sort(dot,dot+len);
else dot[len++]=x.second;
}
cout<<len;
}
算法2介绍
差分数组
其实求分组个数就是求同一个点在不同区间出现的最多次数
朴素算法是设置一个-1e9~1e9的数组,然后遍历所有区间,点出现一次就+1,然后再次遍历一遍
输出max
但是有两个问题 一个是没这么大的空间 另一个是时间有点长
所以我们利用差分数组 这样一个区间整体加1只需要在差分数组的该区间的左端点+1,右端点的下一个下标+1即可
然后遍历整个差分数组 得到max
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<map>
#include<string>
int main(void){
map<int,int> m;
int N,fore,rear;
cin>>N;
while(N--){
cin>>fore>>rear;
m[fore]++;
m[rear+1]--;
}
int res=0,sum=0;
for(auto it=m.begin();it!=m.end();++it){
sum+=it->second;
res=max(sum,res);
}
cout<<res<<endl;
}
算法3介绍
把整个数轴想象成时间轴,区间就是每个活动持续的时间段,问题就转化成了求最少需要多少间教室才能满足给定的这些活动
。
具体我们可以用map[HTML_REMOVED]存储所有活动,time就是这些区间的左端点/右端点
value就是当time是左端点的时候,m[time]++表示在time这个时间点教室数量需要增加一个
当time是右端点的时候 m[time+1]– 表示在time+1这个时间点教室数量释放一个
之所以是time+1是因为给的区间都是闭区间 若出现[2,3],[3,4]那么也需要两个教室
最后遍历所有的端点,看看整个时间轴中,教师数量需要的最大值
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<map>
int main(void){
int N,fore,rear;
cin>>N;
map<int,int> m;
while(N--){
cin>>fore>>rear;
m[fore]++;
m[rear+1]--;
}
int maxv=0;
int room=0;
for(auto it=m.begin();it!=m.end();++it){
room+=it->second;
maxv=max(maxv,room);
}
cout<<maxv;
}
官方算法
按照左端点从小到大排序 依次遍历 若小组中的最小的最右侧的值
比都比当前区间的左端点大
那就新开辟一个小组 否则就添加到这个最小的组
使用小根堆存储开辟的小组的最右侧的值
priority_queue<int,vector<int>,greater<int> > q;
小根堆
priority_queue<int,vector<int>,less<int> > q;
大根堆
#include<iostream>
using namespace std;
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
int main(void){
int N,fore,rear;
cin>>N;
int n=N;
priority_queue<int,vector<int>,greater<int> > q;
vector<pair<int,int> > v;
while(N--){
cin>>fore>>rear;
v.emplace_back(make_pair(fore,rear));
}
sort(v.begin(),v.end());
q.push(v[0].second);
for(int i=1;i<n;i++){
if(v[i].first>q.top()) q.pop();
q.push(v[i].second);
}
cout<<q.size()<<endl;
}