贪心算法实战：活动安排优化（C#语言详解）

为什么贪心策略有效？

对于活动安排问题，贪心策略的核心思想是：优先选择最早结束的活动。这样可以为后续活动留下更多的时间空间，从而最大化安排数量。

这个策略之所以有效，是因为它具有贪心选择性质和最优子结构：

• 贪心选择性质：局部最优（最早结束）能导向全局最优。
• 最优子结构：原问题的最优解包含子问题的最优解。

C# 实现步骤

下面我们用 C# 编写一个完整的活动安排优化程序。我们将定义活动类、排序活动、并应用贪心策略选择活动。

1. 定义活动类

public class Activity{    public string Name { get; set; }    public int Start { get; set; }    public int End { get; set; }    public Activity(string name, int start, int end)    {        Name = name;        Start = start;        End = end;    }    public override string ToString()    {        return $"{Name}: [{Start}, {End}]";    }}

2. 贪心算法实现

using System;using System.Collections.Generic;using System.Linq;class Program{    static void Main()    {        // 示例活动列表        var activities = new List<Activity>        {            new Activity("A1", 1, 4),            new Activity("A2", 3, 5),            new Activity("A3", 0, 6),            new Activity("A4", 5, 7),            new Activity("A5", 8, 9),            new Activity("A6", 5, 9)        };        var selected = SelectActivities(activities);        Console.WriteLine("选中的活动（按结束时间升序）：");        foreach (var act in selected)        {            Console.WriteLine(act);        }    }    // 贪心算法：按结束时间排序后依次选择不冲突的活动    static List<Activity> SelectActivities(List<Activity> activities)    {        // 按结束时间升序排序        var sorted = activities.OrderBy(a => a.End).ToList();        var result = new List<Activity>();        int lastEndTime = -1;        foreach (var activity in sorted)        {            // 如果当前活动的开始时间 >= 上一个选中活动的结束时间            if (activity.Start >= lastEndTime)            {                result.Add(activity);                lastEndTime = activity.End;            }        }        return result;    }}

运行结果说明

以上代码将输出：

选中的活动（按结束时间升序）：A1: [1, 4]A4: [5, 7]A5: [8, 9]

可以看到，我们成功选择了 3 个互不重叠的活动，这是该输入下的最大可能数量。

总结

通过本教程，我们学习了如何使用 C# 贪心算法 解决 活动安排问题。关键在于：按结束时间排序 + 贪心选择。这种方法时间复杂度为 O(n log n)（主要由排序决定），非常高效。

无论你是算法初学者，还是正在准备面试，掌握这个经典案例都能帮助你深入理解 贪心算法 和 活动选择优化 的核心思想。

记住：在合适的问题上使用贪心策略，往往能以最简单的方式获得最优解！