活动选择问题（Activity Selection Problem）是一类经典的贪心算法问题。它涉及一组活动，每个活动有一个开始时间和结束时间，目标是在不重叠的情况下，选择尽可能多的活动。问题可以被表述为：给定一组活动及其开始和结束时间，选择最大数量的相互不重叠的活动，使得它们能够在有限的时间内被安排。

问题描述

给定一组活动 A={a1,a2,…,an}，每个活动 aia_iai​ 都有一个开始时间 si 和结束时间 fi​，其中 si≤fi。我们需要选择一个最大子集 S⊆AS，其中每个活动之间互不重叠，也就是说对于任意 ai,aj∈S （其中 i ），都满足 si≥fj​。

贪心策略

解决活动选择问题的核心是贪心选择策略，即每次都选择最早结束的活动。贪心策略背后的思想是：选择一个最早结束的活动，为后续活动留出更多的时间，从而能够安排更多的活动。这个策略可以通过以下步骤实现：

贪心算法步骤：

1. 将所有活动按照结束时间 fi 进行升序排序。
2. 选择第一个活动（即结束时间最早的活动），将其加入结果集。
3. 对于剩余的活动，选择每个开始时间 sj​ 大于等于上一个选择活动的结束时间 fi 的活动，加入结果集。
4. 重复第 3 步，直到所有活动都被处理完。

贪心算法的正确性证明

• 贪心算法选择的第一个活动是结束时间最早的，后续选择的活动要满足与之前的活动不重叠的要求。
• 如果不选择结束时间最早的活动，而选择了其他活动，会减少后续活动的选择机会，因为这些活动的时间段被较晚结束的活动占用了。
• 通过选择结束时间最早的活动，我们能够最大化剩余可用时间段，从而能够安排更多的活动。

伪代码

1. 让 A 为所有活动的集合，n 为活动数量。
2. 对 A 按照活动结束时间 f_i 进行升序排序。
3. 初始化 result 为空集。
4. 选择第一个活动 a1，并将其加入 result 集合中。
5. 对于每个后续活动 a_j：
    if a_j 的开始时间 s_j ≥ 上一个已选择活动的结束时间：
        将 a_j 加入 result 集合中。
6. 返回 result 集合。

活动选择问题的Java实现

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

class Activity {
    int start, finish;

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

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

        // 第一个活动必然被选择
        System.out.println("选择的活动: ");
        int i = 0;
        System.out.println("活动 " + i + ": (" + activities[i].start + ", " + activities[i].finish + ")");

        // 选择与已选择活动不冲突的活动
        for (int j = 1; j < activities.length; j++) {
            if (activities[j].start >= activities[i].finish) {
                System.out.println("活动 " + j + ": (" + activities[j].start + ", " + activities[j].finish + ")");
                i = j; // 更新已选择的活动
            }
        }
    }

    public static void main(String[] args) {
        // 活动数组，每个活动有开始和结束时间
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(8, 9),
            new Activity(5, 9)
        };

        // 执行活动选择算法
        selectActivities(activities);
    }
}

代码解析

1. 活动表示：Activity 类用来表示每个活动，它有两个属性：开始时间 start 和结束时间 finish。
2. 排序：通过 Arrays.sort() 方法对活动按照结束时间 finish 进行升序排序，这是贪心策略的核心步骤。
3. 活动选择：选择第一个活动，然后遍历后续的活动，选择那些开始时间大于等于上一个已选择活动的结束时间的活动。

输出结果

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

时间复杂度分析

• 排序：排序操作的时间复杂度为 O(nlog⁡n)，其中 n 是活动的数量。
• 选择活动：遍历活动的时间复杂度为 O(n)。
• 因此，总的时间复杂度为 O(nlog⁡n)，主要由排序操作决定。

扩展与应用

1. 会议安排问题：将会议室的使用时间优化，使得最多的会议能够在有限的会议室内举行。
2. 区间调度问题：与活动选择类似，安排尽可能多的区间任务，保证它们互不重叠。
3. CPU作业调度：在有限的时间内，安排尽可能多的作业，使得CPU的使用效率最大化。

贪心策略的适用性

• 局部最优解：贪心算法每一步都选择当前看来最优的解，即最早结束的活动。
• 全局最优解：在活动选择问题中，贪心选择局部最优解可以保证得到全局最优解，因为选择最早结束的活动为后续活动留出了最大可能的时间空间。

贪心算法的局限性

虽然贪心算法在活动选择问题中能够得到最优解，但在其他问题中并不总能得到最优解。因此，使用贪心算法时需要证明它的正确性。

小结

• 活动选择问题是一种典型的贪心算法问题，它要求我们在有限时间内安排最多的活动。
• 贪心算法通过每次选择最早结束的活动来确保能够安排尽可能多的活动。
• 通过将活动按结束时间排序并逐步选择不重叠的活动，可以在 O(nlog⁡n) 的时间复杂度内找到最优解。