活动选择问题详解（用Java实现贪心算法解决区间调度）

什么是活动选择问题？

活动选择问题是一个经典的区间调度问题。给定一组活动，每个活动都有一个开始时间和结束时间。目标是从中选出尽可能多的活动，使得它们在时间上互不重叠（即任意两个活动不能同时进行）。

为什么用贪心算法？

这个问题非常适合使用贪心算法来解决。贪心策略的核心思想是：每一步都做出当前看起来最优的选择，从而希望最终得到全局最优解。

在活动选择问题中，最优的贪心策略是：优先选择结束时间最早的活动。因为这样可以为后续活动留下更多的时间空间，从而可能容纳更多的活动。

Java 实现步骤

下面我们一步步用 Java 来实现这个算法：

1. 定义活动类（包含开始时间和结束时间）
2. 按照结束时间对活动数组进行排序
3. 从第一个活动开始，依次选择与上一个选中活动不冲突的活动

完整 Java 代码示例

import java.util.*;// 定义活动类class Activity {    int start;    int end;    public Activity(int start, int end) {        this.start = start;        this.end = end;    }}public class ActivitySelection {    // 按照结束时间排序    public static void sortActivitiesByEndTime(Activity[] activities) {        Arrays.sort(activities, (a, b) -> Integer.compare(a.end, b.end));    }    // 贪心算法选择最多不重叠活动    public static List<Activity> selectMaxActivities(Activity[] activities) {        if (activities.length == 0) return new ArrayList<>();        sortActivitiesByEndTime(activities);        List<Activity> selected = new ArrayList<>();        selected.add(activities[0]); // 选择第一个结束的活动        int lastSelectedIndex = 0;        for (int i = 1; i < activities.length; i++) {            // 如果当前活动的开始时间 >= 上一个选中活动的结束时间            if (activities[i].start >= activities[lastSelectedIndex].end) {                selected.add(activities[i]);                lastSelectedIndex = i;            }        }        return selected;    }    // 测试方法    public static void main(String[] args) {        Activity[] activities = {            new Activity(1, 4),            new Activity(3, 5),            new Activity(0, 6),            new Activity(5, 7),            new Activity(3, 9),            new Activity(5, 9),            new Activity(6, 10),            new Activity(8, 11),            new Activity(8, 12),            new Activity(2, 14),            new Activity(12, 16)        };        List<Activity> result = selectMaxActivities(activities);        System.out.println("选中的活动（开始时间 - 结束时间）：");        for (Activity a : result) {            System.out.println(a.start + " - " + a.end);        }    }}  

代码解析

• Activity 类用于封装每个活动的开始和结束时间。
• sortActivitiesByEndTime 使用 Lambda 表达式按结束时间升序排序。
• selectMaxActivities 是核心算法：先选结束最早的，然后遍历后续活动，只要不冲突就选。
• 判断是否冲突的条件是：当前活动.start >= 上一个选中活动.end。

时间复杂度分析

排序的时间复杂度是 O(n log n)，选择过程是 O(n)，所以总时间复杂度为 O(n log n)。这是非常高效的解决方案。

总结

通过本教程，我们学习了如何用 贪心算法 解决 活动选择问题，并用 Java实现了完整的解决方案。该问题属于典型的 区间调度 场景，在日程安排、资源分配等领域有广泛应用。

记住关键点：**总是优先选择结束时间最早的活动**，这是获得最多活动数量的最优策略！

提示：你可以尝试修改活动数据，观察输出结果，加深对贪心策略的理解。