貪心算法經典應用二：活動安排問題的 C 語言實現與最優性證明

問題描述

給定 n 個活動，每個活動 i 有開始時間 s_i 和結束時間 f_i (s_i < f_i)，所有活動共享同一資源（如會議室），同一時間只能進行一個活動。若活動 i 與 j 的時間區間 [s_i, f_i) 和 [s_j, f_j) 不相交，則稱它們相容。目標是選出最大相容活動子集，使資源利用率最高。

貪心選擇策略：最早結束時間優先

將所有活動按結束時間 f_i 非遞減排序，然後迭代選擇：

1. 選擇最早結束的活動加入方案；
2. 刪除所有與它衝突的活動；
3. 在剩餘活動中重複上述步驟，直到無活動可選。

這種策略的直觀意義是：選擇最早結束的活動，留給後續活動的可用時間段最長，從而最大化總活動數。

範例數據（已按結束時間排序）

執行演算法可得最優安排：活動 1、4、8、11（共 4 個）。

C 語言完整實現

#include <stdio.h>
#include <stdlib.h>

void greedy(int s[], int f[], int a[], int k);

int main() {
    int s[] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
    int f[] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    int k = sizeof(f) / sizeof(f[0]);
    int *a = (int*)malloc(sizeof(int) * k);

    greedy(s, f, a, k);
    system("PAUSE");
    free(a);
    return 0;
}

/*
 * s[]: 活動開始時間
 * f[]: 活動結束時間（已按非降序排列）
 * a[]: 0/1 標記，1 表示被安排
 * k: 活動總數
 */
void greedy(int s[], int f[], int a[], int k) {
    int i, j = 0;
    for (i = 0; i < k; i++) a[i] = 0;

    a[0] = 1;
    printf("第1個活動被安排\n");
    int count = 1;

    for (i = 1; i < k; i++) {
        if (s[i] >= f[j]) {  // 注意：原代碼用 >，嚴格講應為 >= 才符合區間不相交定義
            a[i] = 1;
            printf("開始%d, 結束%d. 第%d個活動被安排\n", s[i], f[i], i+1);
            j = i;
            count++;
        }
    }
    printf("總計%d個活動被安排\n", count);
}

程式碼關鍵點解析

• 輸入預處理：演算法假設 f[] 已按非降序排序。若輸入無序，需先排序（O(n log n)）。
• 相容性判斷：s[i] >= f[j] 確保新活動開始時間不早於上一被選活動的結束時間。
• 空間複雜度：O(n) 用於標記陣列 a[]。

為什麼貪心策略能得全域最優解？

活動安排問題具有貪心選擇性質與最優子結構。可用數學歸納法證明：

1. 基礎步驟：單一活動時顯然最優。
2. 歸納假設：假設對前 k 個活動，最早結束時間策略產生最優解。
3. 歸納步驟：第 k+1 個活動若與當前最優解相容，加入後仍最優；若不相容，說明其結束時間不早於當前解中某活動，替換不會增加總數。

因此，貪心算法對此問題總能求得整體最優解，這與找零錢問題的「有條件最優」形成鮮明對比。

總結

活動安排問題是貪心算法「總是最優」的教科書級案例。其核心洞見在於：局部最早結束，換取全域最多安排。這一思想廣泛應用於任務調度、CPU 進程排程、頻道分配等領域。