数据结构与算法 / 系统课时

活动选择问题

活动选择问题

本课把贪心选择落到经典的活动选择问题:在同一资源上安排尽可能多的不重叠活动。你将看到“最早结束”如何通过排序和一次扫描构造剩余子问题,并用可运行的 Java 程序验证选择结果。

学习目标

  • 将活动区间转换为可排序、可判定兼容性的输入。
  • 实现按结束时间升序选择活动的贪心算法。
  • 使用交换论证解释算法正确性,并分析时间与空间复杂度。

问题定义与选择规则

每个活动用半开区间 [start, end) 表示,占用同一个会议室或处理器。两个活动兼容,当且仅当前一个活动结束后,后一个活动才开始,即 next.start >= lastEnd。目标是在所有活动中选出数量最多的兼容子集。

贪心规则是:在当前仍可选择的活动中,优先选择结束时间最早的活动。结束越早,留给后续活动的时间范围越大,因此不会比选择一个结束更晚的活动更差。

执行过程

  1. 按 end 从小到大排序;结束时间相同时,可再按 start 排序以获得稳定、可预测的顺序。
  2. 选择排序后的第一个兼容活动,并把其结束时间记录为 lastEnd。
  3. 从左到右扫描剩余活动;若 start >= lastEnd,就接受该活动并更新 lastEnd。
  4. 扫描结束后,已选择列表就是一个最大数量的兼容活动集合。

活动选择的时间轴与扫描过程

以下是部分扫描决策。半开区间允许一个活动在另一个活动结束的同一时刻开始。

活动 区间 当前 lastEnd 处理结果
A1 [1,4) 初始 选择,更新为 4
A2 [3,5) 4 拒绝,开始时间过早
A4 [5,7) 4 选择,更新为 7
A8 [8,11) 7 选择,更新为 11
A11 [12,16) 11 选择,更新为 16

正确性与复杂度

设贪心算法首先选择结束最早的活动 G,任取一个最优方案,其第一个活动为 O。因为 G.end <= O.end,用 G 替换 O 后,不会减少后续可用时间,也不会使原本兼容的后续活动失效。因此至少存在一个最优方案以 G 开头。

选择 G 后,只需在开始时间不早于 G.end 的活动中继续解决同样的问题,这构成最优子结构。对剩余活动重复交换论证,就能得到完整的最优选择序列。

排序需要 O(n log n) 时间,线性扫描需要 O(n) 时间。示例为了不修改原列表而复制数据,额外空间为 O(n);若允许原地排序,除结果列表外可减少辅助空间。

完整可运行示例

程序使用 Java record 表示活动,先复制并排序输入,再执行一次兼容性扫描。将代码保存为 ActivitySelectionDemo.java。

java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class ActivitySelectionDemo {

    record Activity(String name, int start, int end) {
        @Override
        public String toString() {
            return name + "[" + start + "," + end + ")";
        }
    }

    static List<Activity> selectMaximumCompatible(List<Activity> activities) {
        List<Activity> sorted = new ArrayList<>(activities);
        sorted.sort(Comparator.comparingInt(Activity::end)
                .thenComparingInt(Activity::start));

        List<Activity> selected = new ArrayList<>();
        int lastEnd = Integer.MIN_VALUE;

        // 结束最早的兼容活动会为后续活动留下最大的时间空间。
        for (Activity activity : sorted) {
            if (activity.start() >= lastEnd) {
                selected.add(activity);
                lastEnd = activity.end();
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        List<Activity> activities = List.of(
                new Activity("A1", 1, 4),
                new Activity("A2", 3, 5),
                new Activity("A3", 0, 6),
                new Activity("A4", 5, 7),
                new Activity("A5", 3, 9),
                new Activity("A6", 5, 9),
                new Activity("A7", 6, 10),
                new Activity("A8", 8, 11),
                new Activity("A9", 8, 12),
                new Activity("A10", 2, 14),
                new Activity("A11", 12, 16)
        );

        List<Activity> selected = selectMaximumCompatible(activities);
        System.out.println("选择结果: " + selected);
        System.out.println("最多可安排活动数: " + selected.size());
    }
}

编译并运行:

bash
javac ActivitySelectionDemo.java
java ActivitySelectionDemo

预期输出

text
选择结果: [A1[1,4), A4[5,7), A8[8,11), A11[12,16)]
最多可安排活动数: 4

常见错误

1. 按开始时间最早选择

开始得早并不代表结束得早。一个很早开始但持续很久的活动可能阻塞多个短活动,因此该规则不能保证活动数量最大。

2. 按持续时间最短选择

持续时间只描述区间长度,没有反映活动在时间轴上的位置。最短活动可能位于中间,导致前后两侧都无法充分利用。

3. 把兼容条件写成严格大于

使用半开区间 [start, end) 时,start == lastEnd 表示两个活动首尾相接,应该允许选择。若误写为 start > lastEnd,会丢失合法活动。

4. 忘记先排序

直接按输入顺序扫描,只能得到该顺序下的一个可行解,不能保证数量最大。验证时可打乱输入顺序,确认排序后的结果仍保持一致。

本课练习

  1. 将示例中的活动 A4 改为 [4,7),重新运行程序并解释结果是否变化。验收条件是说明半开区间兼容规则如何影响选择。
  2. 扩展程序,使其在结束时间相同的活动中优先选择开始时间更晚的活动,并验证最大活动数量是否改变。验收条件是输出选择序列,并说明该次级排序只影响哪一部分结果。

本课总结

  • 活动选择问题通过“按结束时间升序排序,再接受兼容活动”得到最大数量的区间集合。
  • 结束最早的活动可以通过交换论证安全地替换最优方案中的第一个活动。
  • 算法的主要成本来自排序,总时间复杂度为 O(n log n),扫描阶段为 O(n)。

下一课预告

下一阶段将继续学习如何识别可证明的贪心选择,并把排序、局部决策和交换论证应用到资源分配、编码与图结构问题中。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

活动选择问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通