贪心算法详解：活动选择问题（C#语言实现与小白入门教程）

什么是活动选择问题？

假设你是一个会议室管理员，每天有很多人申请使用会议室举办活动。每个活动都有一个开始时间和结束时间。你的任务是安排尽可能多的互不冲突的活动（即任意两个活动的时间不能重叠）。这就是著名的活动选择问题。

例如：

• 活动A：9:00 - 10:30
• 活动B：10:00 - 11:00
• 活动C：11:00 - 12:00

显然，A 和 B 冲突，但 A 和 C 不冲突。所以最多可安排两个活动：A 和 C。

为什么用贪心算法？

这个问题具有贪心选择性质和最优子结构，非常适合用贪心算法解决。关键在于：**总是优先选择最早结束的活动**。这样可以为后续活动留下最多的时间空间，从而最大化活动数量。

C# 实现步骤

我们将按以下步骤实现：

1. 定义活动类（包含开始时间、结束时间）
2. 按结束时间对活动排序
3. 遍历排序后的活动列表，选择不冲突的活动

完整 C# 代码示例

using System;using System.Collections.Generic;using System.Linq;class Activity{    public string Name { get; set; }    public int Start { get; set; }    public int Finish { get; set; }    public Activity(string name, int start, int finish)    {        Name = name;        Start = start;        Finish = finish;    }}class Program{    static void Main()    {        // 创建活动列表        List<Activity> activities = new List<Activity>        {            new Activity("A", 1, 4),            new Activity("B", 3, 5),            new Activity("C", 0, 6),            new Activity("D", 5, 7),            new Activity("E", 8, 9),            new Activity("F", 5, 9)        };        // 按结束时间升序排序        var sortedActivities = activities.OrderBy(a => a.Finish).ToList();        Console.WriteLine("选中的活动：");        SelectActivities(sortedActivities);    }    static void SelectActivities(List<Activity> activities)    {        if (activities.Count == 0) return;        // 第一个活动总是被选中（因为它结束最早）        Activity lastSelected = activities[0];        Console.WriteLine(lastSelected.Name);        // 从第二个活动开始遍历        for (int i = 1; i < activities.Count; i++)        {            // 如果当前活动的开始时间 >= 上一个选中活动的结束时间            if (activities[i].Start >= lastSelected.Finish)            {                Console.WriteLine(activities[i].Name);                lastSelected = activities[i];            }        }    }}

代码解析

1. Activity 类用于表示每个活动，包含名称、开始时间和结束时间。

2. 使用 OrderBy(a => a.Finish) 对活动按结束时间升序排序——这是贪心策略的核心。

3. 在 SelectActivities 方法中，我们首先选择第一个活动（结束最早），然后依次检查后续活动是否与上一个选中的活动冲突（即当前活动的开始时间 ≥ 上一个活动的结束时间）。

运行上述代码，输出为：

选中的活动：ADE

总结

通过本教程，我们学习了如何使用 贪心算法 解决 活动选择问题，并用 C# 实现 了完整的解决方案。这种思路不仅适用于会议室调度，还可用于课程安排、任务调度等实际场景。

记住贪心算法的关键：**局部最优选择 → 全局最优解**（前提是问题具备贪心选择性质）。希望这篇 算法教程 能帮助你迈出算法学习的第一步！

继续练习，你也能成为算法高手！