题解:UVA11776 Oh Your Royal Greediness!

封面

简要题意:

多组数据。

每组数据给定 nn0n10000 \le n \le 1000)个区间 [si,ei][s_i,e_i]0siei315360000 \le s_i \le e_i \le 31536000),求所有时刻中同时存在的区间数量的最大值。

思路:

考虑扫描线算法。

对于扫描线的基本步骤,可以参考此博文

将每个区间的开始点和结束点存下来,然后按照时间顺序排序,如果是起点让计数器加一,否则是终点让计数器减一,我们只需要在计算器里取最大值就好了。

因为终点也算在区间里,所以我们在处理时要优先处理起点。

对于每组数据,时间复杂度为 O(nlogn)O(n \log n)

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int n;
int Case_Cnt=0;
struct node{
int x,lx;
friend bool operator<(node x,node y){
return x.x!=y.x?x.x<y.x:x.lx>y.lx;
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
while(cin>>n){
if(n==-1)break;
int ans=0;
cout<<"Case "<<++Case_Cnt<<": ";
vector<node>sz;
for(int i=1;i<=n;i++){
int s,e;
cin>>s>>e;
sz.emplace_back(node{s,1});
sz.emplace_back(node{e,-1});
}
sort(sz.begin(),sz.end());
int now=0;
for(int i=0;i<n*2;i++){
ans=max(ans,now);
now+=sz[i].lx;
}
ans=max(ans,now);
cout<<ans<<"\n";
}
return 0;
}