经典贪心问题 - 活动选择问题

1. 问题描述

活动选择问题是一个经典的贪心算法问题。给定一系列活动，每个活动都有开始时间和结束时间。我们需要选择不重叠的活动，使得选择的活动数量最大。活动可以看作是一种“时间区间”，我们的目标是在这些活动中选择出尽可能多的活动，且这些活动之间没有时间上的重叠。

举个例子：

假设有以下几个活动及其开始和结束时间：

目标是选择最大数量的不重叠活动。例如，选择活动 A 和活动 D，因为它们之间没有时间上的重叠。

2. 贪心算法的选择标准

在贪心算法中，我们的目标是每次选择最优解。对于活动选择问题，贪心算法的选择标准是：

每次选择结束时间最早的活动：

这样做的理由是，当选择一个结束时间最早的活动时，会留下尽可能多的时间给后续活动。由于我们每次选择的活动是结束时间最早的，因此我们每次选择的活动和后续活动的重叠机会最小，从而能选择更多不重叠的活动。

3. 实现步骤与代码解析

步骤：

1. 对活动按结束时间排序： 首先，我们需要对活动按照结束时间进行排序。排序后的活动能够帮助我们快速选择结束时间最早的活动，从而保证贪心选择的最优性。

2. 选择活动： 从排序后的活动列表中，选择结束时间最早的活动。如果该活动与已经选择的活动不重叠，则选择该活动。

3. 迭代选择： 继续选择下一个不与已选择活动重叠的活动，直到所有活动都被处理完。

Java代码实现：

import java.util.Arrays;
import java.util.Comparator;

public class ActivitySelection {

    // 活动类
    static class Activity {
        int start, end;

        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    // 贪心算法解决活动选择问题
    public static void selectActivities(Activity[] activities) {
        // 按活动结束时间排序
        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));

        System.out.println("选择的活动：");
        // 选择第一个活动
        int lastSelected = 0;
        System.out.println("活动 " + lastSelected + ": (" + activities[lastSelected].start + ", " + activities[lastSelected].end + ")");
        
        // 遍历剩下的活动
        for (int i = 1; i < activities.length; i++) {
            // 如果活动i的开始时间大于等于上一个选择的活动的结束时间，说明不重叠
            if (activities[i].start >= activities[lastSelected].end) {
                lastSelected = i;
                System.out.println("活动 " + lastSelected + ": (" + activities[lastSelected].start + ", " + activities[lastSelected].end + ")");
            }
        }
    }

    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)
        };

        // 调用贪心算法选择活动
        selectActivities(activities);
    }
}

代码解析：

1. 定义活动类：首先定义一个 Activity 类来表示每个活动的开始时间和结束时间。

2. 排序活动：使用 Arrays.sort() 方法根据活动的结束时间对活动数组进行排序。排序后的活动按结束时间从早到晚排列。

3. 选择活动：从排序后的活动中，首先选择第一个活动，然后遍历剩余的活动。对于每个活动，如果它的开始时间大于等于已选择活动的结束时间，则选择该活动。这样确保活动之间不重叠。

4. 输出结果：每次选择活动时，打印出被选择的活动。

输出结果：

选择的活动：
活动 0: (1, 4)
活动 3: (5, 7)

在这个例子中，按照贪心算法选择的活动是活动 0 和活动 3，它们的时间不重叠，且总数量是最大的。

4. 时间复杂度分析

1. 排序时间复杂度：对活动按结束时间进行排序的时间复杂度为 O(n log n)，其中 n 是活动的数量。

2. 选择活动的时间复杂度：选择活动时，我们只需要遍历一次活动数组，时间复杂度为 O(n)。

3. 整体时间复杂度：由于排序的时间复杂度占主导，整体时间复杂度为 O(n log n)。

5. 总结

活动选择问题是一个经典的贪心算法问题。通过每次选择结束时间最早的活动，贪心算法能够最大化选择不重叠的活动。贪心算法的关键在于找到合适的选择标准，这个标准能够保证每一步的选择都是局部最优解，并最终得到全局最优解。在这个问题中，选择结束时间最早的活动是最合适的标准。

活动选择问题的时间复杂度为 O(n log n)，主要受排序过程的影响。通过这个问题，我们可以更好地理解贪心算法的设计思想和应用场景。