會場安排問題：貪心算法解決區間不重疊排程

會場安排問題：貪心算法解決區間不重疊排程

學校禮堂每天都有許多活動申請使用，但這些活動的時間經常發生衝突。小劉的任務是安排這些活動，使得在同一時間段內最多只能舉行一場活動，並且要盡可能安排更多的活動。這是一個經典的區間調度問題，可以用貪心算法高效求解。

問題描述

給定 n 個活動，每個活動有起始時間 Bᵢ 和結束時間 Eᵢ (Bᵢ ≤ Eᵢ)。若上一個活動在時間 t 結束，下一個活動最早需在 t+1 才能開始。目標是選出最多數量的不重疊活動。

輸入輸出格式

• 第一行：測試組數 m (m < 100)
• 每組第一行：活動數 n (1 < n < 10000)
• 接下來 n 行：每行兩個整數 Bᵢ, Eᵢ (0 ≤ Bᵢ, Eᵢ < 10000)
• 輸出：每組一行，最多能安排的活動數量

貪心策略與證明

核心思想：優先選擇結束時間最早的活動。這樣能為後續活動留出更多可用時間，從而最大化總活動數。

1. 將所有活動按結束時間 Eᵢ 升序排序
2. 選擇第一個活動（結束最早）
3. 遍歷剩餘活動，若當前活動的起始時間 ≥ 上一個被選活動的結束時間 + 1，則選擇它
4. 重複直到所有活動處理完畢

時間複雜度分析

• 排序：O(n log n)
• 掃描：O(n)
• 總體：O(n log n)，滿足 n < 10000 的要求

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

struct Activity {
    int start, end;
};

bool cmp(const Activity &a, const Activity &b) {
    return a.end < b.end;
}

int main() {
    int m; scanf("%d", &m);
    while (m--) {
        int n; scanf("%d", &n);
        vector<Activity> acts(n);
        for (int i = 0; i < n; ++i)
            scanf("%d %d", &acts[i].start, &acts[i].end);
        
        sort(acts.begin(), acts.end(), cmp);
        
        int cnt = 1, last_end = acts[0].end;
        for (int i = 1; i < n; ++i) {
            if (acts[i].start >= last_end + 1) {
                ++cnt;
                last_end = acts[i].end;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

關鍵點總結

• 排序關鍵：按結束時間而非開始時間
• 邊界條件：下一活動需 ≥ 前一結束時間 + 1
• 貪心選擇性質：局部最優（最早結束）導致全域最優

此問題是貪心算法在區間調度中的典型應用，同樣適用於會議室分配、任務調度等實際場景。