C語言貪心算法實現：活動安排問題（區間調度最大化）

問題描述

給定 n 個活動，每個有開始時間 sᵢ 和結束時間 fᵢ。選擇最大子集，使任兩活動不重疊（即 sⱼ ≥ fᵢ 或 sᵢ ≥ fⱼ）。

貪心策略

按結束時間 fᵢ 遞增排序，依序選擇：第一個必選，之後若某活動開始時間 ≥ 最後被選活動的結束時間，則選擇它。

完整實現（兩種排序版本）

版本一：氣泡排序（固定 11 個活動）

struct Object { int id, start, finish; };

void Sort(struct Object a[], int n) {
    for (int i=0; i<n; i++)
        for (int j=0; j<n-i-1; j++)
            if (a[j].finish > a[j+1].finish) swap(a[j], a[j+1]);
}

int GreedySelector(struct Object a[], int n) {
    int count = 1, last = 0;
    for (int i=1; i<n; i++)
        if (a[i].start >= a[last].finish) {
            count++; last = i;
        }
    return count;
}

版本二：快速排序（通用 n）

typedef struct { int start, finish, number; } arrange;
arrange plans[MAX];

int partition(arrange a[], int p, int q) {
    int i=p, j=q+1;
    while (1) {
        do i++; while (a[i].finish < a[p].finish && i<q);
        do j--; while (a[j].finish > a[p].finish);
        if (i<j) swap(a[i], a[j]); else break;
    }
    swap(a[p], a[j]); return j;
}

void quicksort(arrange a[], int p, int q) {
    if (p<q) { int j=partition(a,p,q); quicksort(a,p,j-1); quicksort(a,j+1,q); }
}

int greedySelector(arrange p[], int n) {
    int count=1, last=0;
    for (int i=1; i<n; i++)
        if (p[i].start >= p[last].finish) { count++; last=i; }
    return count;
}

測試資料與結果

11 活動:
1: 1-4   2: 3-5   3: 0-6   4: 5-7   5: 3-8
6: 5-9   7: 6-10  8: 8-11  9: 8-12  10: 2-13
11: 12-14

排序後結束時間: 4,5,6,7,8,9,10,11,12,13,14
貪心選擇: 1(1-4) → 4(5-7) → 8(8-11) → 11(12-14)
最多 4 個活動

正確性證明要點

1. 貪心選擇性質：最早結束的活動一定存在於某個最優解中（若最優解第一個活動非最早結束，可替換而不減少總數）。
2. 最優子結構：選擇第一個活動後，剩餘問題為相同子問題（從相容活動中繼續選）。

應用場景

• 會議室排程、CPU 任務調度、頻道分配、影片剪輯片段選取。
• 若活動有權重（優先級），需改用動態規劃（加權區間調度）。

複雜度

• 排序：O(n log n)（快排/歸併）或 O(n²)（氣泡）。
• 掃描選擇：O(n)。
• 總計：O(n log n)。

活動安排問題是貪心算法「最早結束時間優先」策略的標準範例，展示了如何將區間衝突轉化為排序後的線性掃描，極具工程實用價值。