UVA 11776 - Oh Your Royal Greediness! (區間最大重疊 - 掃描線)

問題描述

同 UVA 11776（另一編號）：N 個農民區間 [S,E]，監工同一時間只能看一個，求最少監工數。即區間最大重疊數。

掃描線算法

1. 事件：(S, +1), (E, -1)。區間包含兩端，故離開事件排在同坐標進入事件之後（排序時 +1 優先）。
2. 按時間排序，掃描累加，維護最大值。

完整代碼

#include <bits/stdc++.h>
using namespace std;
struct Event { int t, d; bool operator<(const Event& o) const { return t!=o.t ? to.d; } };
int main() {
    int n, cas=1;
    while(cin>>n && n!=-1) {
        vector ev;
        for(int i=0;i>s>>e;
            ev.push_back({s,1});
            ev.push_back({e,-1});
        }
        sort(ev.begin(), ev.end());
        int cur=0, ans=0;
        for(auto &e: ev) {
            cur += e.d;
            ans = max(ans, cur);
        }
        cout << "Case " << cas++ << ": " << ans << endl;
    }
    return 0;
}

複雜度

O(N log N)，N≤1000 極快。