掌握Rust中的贪心算法（从零开始的Rust贪心算法实战教程）

实战案例：活动选择问题

假设你有一系列会议（活动），每个会议有开始时间和结束时间。你的目标是参加尽可能多的会议，但不能同时参加两个时间重叠的会议。这就是经典的活动选择问题，非常适合用贪心算法解决。

贪心策略

我们的策略是：优先选择结束时间最早的活动。因为这样可以为后续活动留下最多的时间空间。

Rust代码实现

下面是一个完整的Rust程序，演示如何使用贪心算法解决活动选择问题：

// 定义活动结构体#[derive(Debug, Clone)]struct Activity {    start: i32,    end: i32,}// 贪心算法：选择最大数量的不重叠活动fn select_activities(mut activities: Vec<Activity>) -> Vec<Activity> {    // 按结束时间升序排序    activities.sort_by_key(|a| a.end);        let mut selected = Vec::new();    let mut last_end_time = 0;        for activity in activities {        // 如果当前活动的开始时间 >= 上一个选中活动的结束时间        if activity.start >= last_end_time {            selected.push(activity);            last_end_time = activity.end;        }    }        selected}fn main() {    let activities = vec![        Activity { start: 1, end: 4 },        Activity { start: 3, end: 5 },        Activity { start: 0, end: 6 },        Activity { start: 5, end: 7 },        Activity { start: 3, end: 9 },        Activity { start: 5, end: 9 },        Activity { start: 6, end: 10 },        Activity { start: 8, end: 11 },        Activity { start: 8, end: 12 },        Activity { start: 2, end: 14 },        Activity { start: 12, end: 16 },    ];        let result = select_activities(activities);    println!("选中的活动（按结束时间排序）:");    for act in result {        println!("开始: {}, 结束: {}", act.start, act.end);    }}

代码解析

• 排序：首先将所有活动按结束时间升序排列，这是贪心策略的关键一步。
• 遍历选择：从第一个活动开始，只要当前活动的开始时间不早于上一个选中活动的结束时间，就将其加入结果集。
• 效率：时间复杂度主要由排序决定，为 O(n log n)，非常高效。

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

直觉上，选择结束最早的活动能为后面留出最多时间。数学上可以证明：对于活动选择问题，这种贪心选择具有最优子结构和贪心选择性质，因此能得到全局最优解。

总结与进阶

通过本教程，你已经掌握了Rust中实现贪心算法的基本方法。记住，Rust算法教程的核心不仅是写代码，更是理解问题背后的逻辑。接下来你可以尝试：

• 修改代码以处理边界情况（如空活动列表）
• 尝试其他贪心问题，如“找零钱”（注意：只有特定币值系统才适用贪心）
• 对比动态规划解法，理解贪心与DP的区别

贪心算法是贪心策略编程的重要组成部分，掌握它将大大提升你解决实际问题的能力。继续练习，你很快就能在Rust中游刃有余地应用各种算法了！