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

問題描述

N 個農民，每個有作物生長區間 [S, E]。一名監工同一時間只能看管一個農民。求最少需要多少監工才能覆蓋所有農民的生長期。

本質：求區間最大重疊數（同一時刻最多有多少區間同時存在）。

解法一：暴力枚舉右端點 O(N²)

對每個區間的右端點 E，統計有多少區間滿足 S_i ≤ E ≤ E_i，取最大值。N≤1000 可通過。

解法二：掃描線 O(N log N) - 推薦

1. 將所有端點拆分為事件：(S, +1), (E, -1)。注意：若區間包含端點，離開時刻應為 E+ε，排序時同坐標 +1 在 -1 前。
2. 按時間排序，掃描累加計數，維護最大值。

完整代碼 (掃描線)

#include <bits/stdc++.h>
using namespace std;
struct Event { int t, delta; bool operator<(const Event& o) const { return t!=o.t ? to.delta; } };
int main() {
    int n, cas=1;
    while(scanf("%d",&n)==1 && n!=-1) {
        vector ev;
        for(int i=0;i

複雜度
時間 O(N log N)，空間 O(N)。暴力 O(N²) 亦可接受 (N≤1000)。