Go语言中的贪心算法实战（详解活动选择问题）

为什么用贪心算法？

贪心算法的核心思想是：每一步都做出当前看起来最优的选择，希望最终结果也是全局最优的。

对于活动选择问题，一个经典的贪心策略是：优先选择结束时间最早的活动。因为这样能为后续活动留下最多的时间空间。

这个策略已被证明能得到最优解！

Go语言实现步骤

下面我们用 Go 一步步实现这个算法。

1. 定义活动结构

type Activity struct {    Start int    End   int}

2. 按结束时间排序

我们需要先将所有活动按结束时间升序排列。

import "sort"// 按结束时间排序sort.Slice(activities, func(i, j int) bool {    return activities[i].End < activities[j].End})

3. 贪心选择活动

从第一个活动开始，每次选择结束时间最早且与上一个选中活动不冲突的活动。

func selectActivities(activities []Activity) []Activity {    if len(activities) == 0 {        return []Activity{}    }    // 按结束时间排序    sort.Slice(activities, func(i, j int) bool {        return activities[i].End < activities[j].End    })    selected := []Activity{activities[0]}    lastEnd := activities[0].End    for i := 1; i < len(activities); i++ {        // 如果当前活动的开始时间 >= 上一个选中活动的结束时间        if activities[i].Start >= lastEnd {            selected = append(selected, activities[i])            lastEnd = activities[i].End        }    }    return selected}

4. 完整可运行示例

package mainimport (    "fmt"    "sort")type Activity struct {    Start int    End   int}func selectActivities(activities []Activity) []Activity {    if len(activities) == 0 {        return []Activity{}    }    sort.Slice(activities, func(i, j int) bool {        return activities[i].End < activities[j].End    })    selected := []Activity{activities[0]}    lastEnd := activities[0].End    for i := 1; i < len(activities); i++ {        if activities[i].Start >= lastEnd {            selected = append(selected, activities[i])            lastEnd = activities[i].End        }    }    return selected}func main() {    activities := []Activity{        {1, 4},        {3, 5},        {0, 6},        {5, 7},        {3, 9},        {5, 9},        {6, 10},        {8, 11},        {8, 12},        {2, 14},        {12, 16},    }    result := selectActivities(activities)    fmt.Println("选中的活动（开始-结束）：")    for _, act := range result {        fmt.Printf("[%d, %d]\n", act.Start, act.End)    }}

运行结果：

选中的活动（开始-结束）：[1, 4][5, 7][8, 11][12, 16]

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

关键在于：结束时间越早，留给后面的时间就越多。即使存在其他组合能选出同样数量的活动，但“最早结束”策略永远不会比最优解差。

这属于贪心算法的经典应用场景——具有贪心选择性质和最优子结构的问题。

总结

通过本教程，我们学习了如何在Go语言中使用贪心算法解决活动选择问题。整个过程包括：定义数据结构、排序、贪心选择，并验证了其正确性。

记住：贪心算法虽快（时间复杂度 O(n log n)，主要来自排序），但并非适用于所有问题。只有当问题具备贪心选择性质时，才能保证得到最优解。

希望这篇算法教程对你有所帮助！动手试试修改活动列表，看看结果如何变化吧。