活动选择问题

给定 n 个互斥占用同一资源的活动，每个活动包含指定的开始时间与结束时间，要求在所有活动中挑选出一个互不冲突且数量最多的活动集合。

January 1, 1990区间调度问题1分钟阅读

活动选择问题贪心算法示意图，讲解最多互不重叠活动的求解思路，包含流程图与时间轴示例

假设你手头有 $n$ 个活动，集合记为 $S = \{a_1, a_2, \dots, a_n\}$ 。每个活动都需要占用同一个场地/资源（例如同一间会议室），因此同一时间只能举办一个活动。

每个活动 $a_i$ 都有一个开始时间 $s_i$ 和 结束时间 $f_i$ ，占用时间段为半开区间 $[s_i, f_i)$ 。

如果两个活动 $a_i$ 和 $a_j$ 的时间段完全不重叠（即 $s_i \ge f_j$ 或 $s_j \ge f_i$ ），则称它们是兼容的（Compatible）。

目标：从所有活动中挑选出一个互兼容的活动集合，使得该集合包含的活动数量最多。

面对这个问题，直觉上可能会提出多种“贪心选择”标准，但并非所有的贪心策略都能得到正确答案：

尝试策略	具体思路	是否可行	反例 / 原因
策略 A：选持续时间最短的	优先安排占用时间少（ $f_i - s_i$ 最小）的活动	失败	假设有活动 $[1, 10]$ ，以及短活动 $[1, 5]$ 、 $[4, 7]$ 、 $[6, 10]$ 。选最短的 $[4, 7]$ 会导致只能选 1 个，而实际可选 2 个（ $[1, 5]$ 和 $[6, 10]$ ）。
策略 B：选与其它活动冲突最少的	优先安排与剩余活动重叠次数最少的活动	失败	存在复杂的反例结构，容易陷入局部最优陷阱。
策略 C：选开始时间最早的	优先安排 $s_i$ 最小的活动	失败	若最早开始的活动持续极其漫长（如 $[1, 100]$ ），会挤占后续所有活动。
策略 D：选结束时间最早的	优先安排 $f_i$ 最小且与已选活动不冲突的活动	成功	正确策略。最早结束意味着给后续活动留出了尽可能多的自由时间。

为什么“按结束时间最早选择”一定能得到全局最优解？我们可以使用反证法 / 剪枝与替换法进行证明：

基本前提：我们将所有活动按结束时间 $f_i$ 从小到大排序，假设 $a_1$ 是结束时间最早的活动。
假设存在最优解 $O$ ：假设 $O$ 是一个最优活动集合，但 $O$ 中的第一个活动不是 $a_1$ ，而是某个活动 $a_k$ ( $k \neq 1$ )。
构造新解 $O'$ ：因为 $a_1$ 是所有活动中结束最早的，所以必然有 $f_1 \le f_k$ 。如果我们用 $a_1$ 替换掉 $O$ 中的 $a_k$ ，得到一个新的集合 $O' = (O \setminus \{a_k\}) \cup \{a_1\}$ 。
推导兼容性：因为 $a_1$ 比 $a_k$ 结束得更早，所以 $a_1$ 绝不会与 $O$ 中 $a_k$ 之后的任何活动发生冲突。因此 $O'$ 依然是一个完全互兼容的活动集合。
结论： $O'$ 包含的活动数量与 $O$ 相同，说明 $O'$ 同样也是全局最优解。这证明了：第一步选择结束时间最早的活动 $a_1$ ，绝对不会错过全局最优解（满足贪心选择性质）。

排序：将 $n$ 个活动按结束时间 $f_i$ 升序排序。
选择：
- 默认挑选第一个活动 $a_1$ ，并记录其结束时间 $last\_f = f_1$ 。
- 遍历剩余活动，若当前活动 $a_i$ 的开始时间 $s_i \ge last\_f$ ，则将 $a_i$ 加入结果集，并更新 $last\_f = f_i$ 。

时间复杂度：主要是排序开销，为 $O(n \log n)$ 。遍历筛选阶段仅需 $O(n)$ 。
空间复杂度：若原地排序且只记录活动索引，辅助空间为 $O(1)$ 。

#include <iostream>
#include <vector>
#include <algorithm>

struct Activity {
    int id;
    int start;
    int finish;
};

// 比较函数：按结束时间升序排序
bool compareActivity(const Activity& a, const Activity& b) {
    return a.finish < b.finish;
}

std::vector<Activity> selectActivities(std::vector<Activity>& activities) {
    std::vector<Activity> result;
    if (activities.empty()) return result;

    // 1. 按结束时间排序
    std::sort(activities.begin(), activities.end(), compareActivity);

    // 2. 贪心挑选：首选第一个结束的活动
    result.push_back(activities[0]);
    int lastFinishTime = activities[0].finish;

    // 3. 依次遍历后续活动
    for (size_t i = 1; i < activities.size(); ++i) {
        if (activities[i].start >= lastFinishTime) {
            result.push_back(activities[i]);
            lastFinishTime = activities[i].finish; // 更新最后结束时间
        }
    }

    return result;
}

int main() {
    std::vector<Activity> activities = {
        {1, 1, 4}, {2, 3, 5}, {3, 0, 6}, {4, 5, 7},
        {5, 3, 9}, {6, 5, 9}, {7, 6, 10}, {8, 8, 11},
        {9, 8, 12}, {10, 2, 14}, {11, 12, 16}
    };

    auto selected = selectActivities(activities);

    std::cout << "最多可安排的活动数量: " << selected.size() << "\n安排的活动序列: ";
    for (const auto& act : selected) {
        std::cout << "a" << act.id << " [" << act.start << "," << act.finish << ") ";
    }
    std::cout << std::endl;

    return 0;
}

加权活动选择问题
- 变化：每个活动除了时间外，还附带一个价值/权重 $w_i$ ，目标是使选出的活动总价值最大（而不是数量最多）。
- 解决：贪心选择性质在此失效，必须改用动态规划（DP），结合二分查找在 $O(n \log n)$ 时间内求解。
无重叠区间
- 变化：计算最少需要移除多少个区间，才能使剩余区间互不重叠。
- 解决：等价于 总区间数 - 最多可保留的兼容区间数（活动选择问题）。

贪心策略与直觉探讨

正确性证明（剪枝与替换法）

算法实现步骤与复杂度

步骤

复杂度分析

参考代码

变体与延伸