题解：UVA11776 Oh Your Royal Greediness!

xyx404 · 2025-07-17 10:48:36 · 题解

简要题意：

多组数据。

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

思路：

考虑扫描线算法。

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

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

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

对于每组数据，时间复杂度为 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;
}