掌握C语言贪心算法（从零开始的贪心策略实战指南）

经典案例：活动选择问题

假设你有一个会议室，一天内有多个活动申请使用。每个活动都有开始时间和结束时间。你的目标是安排尽可能多的活动，且它们之间不能时间重叠。

这个问题非常适合用贪心算法解决。我们的贪心策略是：优先选择结束时间最早的活动。因为这样可以为后面的活动留下最多的时间空间。

步骤如下：

1. 将所有活动按结束时间升序排序。
2. 选择第一个活动（结束最早）。
3. 从剩下的活动中，选择下一个开始时间不早于上一个选中活动结束时间的活动。
4. 重复此过程，直到没有活动可选。

C语言实现

下面是一个完整的C语言算法入门级别的实现代码：

#include <stdio.h>#include <stdlib.h>// 活动结构体typedef struct {    int start;    int end;} Activity;// 比较函数：用于qsort，按结束时间升序排序int compare(const void* a, const void* b) {    Activity* actA = (Activity*)a;    Activity* actB = (Activity*)b;    return (actA->end - actB->end);}int main() {    // 示例活动数据：{开始时间, 结束时间}    Activity activities[] = {        {1, 4}, {3, 5}, {0, 6}, {5, 7},        {3, 9}, {5, 9}, {6, 10}, {8, 11},        {8, 12}, {2, 14}, {12, 16}    };        int n = sizeof(activities) / sizeof(activities[0]);        // 按结束时间排序    qsort(activities, n, sizeof(Activity), compare);        printf("选中的活动（按结束时间排序后）:\n");        int last_end = -1;    for (int i = 0; i < n; i++) {        if (activities[i].start >= last_end) {            printf("活动 %d: [%d, %d]\n", i + 1, activities[i].start, activities[i].end);            last_end = activities[i].end;        }    }        return 0;}  

运行结果说明

程序会输出被选中的活动列表。例如：

选中的活动（按结束时间排序后）:活动 1: [1, 4]活动 4: [5, 7]活动 8: [8, 11]活动 11: [12, 16]  

为什么这个贪心策略有效？

因为我们总是优先选择结束最早的活动，这为后续活动留出了最大可能的时间窗口。数学上可以证明，这种策略在活动选择问题中能得到最优解。

总结

通过本教程，你应该已经掌握了C语言贪心算法的基本思想和实现方法。记住，贪心算法的关键在于：问题是否具有贪心选择性质和最优子结构。不是所有问题都适合用贪心，但在合适的问题上，它往往简洁高效。

希望这篇贪心算法教程能帮助你迈出C语言算法入门的重要一步！继续练习更多贪心问题（如找零钱、背包问题变种等），你会越来越熟练。

关键词回顾：C语言贪心算法、贪心算法教程、贪心策略、C语言算法入门