1751. 最多可以参加的会议数目 II

发表于 2026-01-13 分类于力扣阅读次数： Waline：本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

状态机DP
线性DP
划分DP
二分
排序

思路

一、问题描述与抽象建模

给定若干个活动，每个活动由三元组表示： \[ (s_i, e_i, v_i) \]

\(s_i\)：活动开始时间
\(e_i\)：活动结束时间（包含当天）
\(v_i\)：参加该活动获得的价值

要求在 最多选择 \(k\) 个活动 的前提下，使得所选活动 两两时间不重叠（即前一个活动的结束时间严格小于下一个活动的开始时间），并最大化总价值。

二、关键建模思想：排序 + 区间 DP

1. 按结束时间排序

将所有活动按结束时间 \(e_i\) 升序排序（若结束时间相同，则按开始时间升序）。

排序后具有如下重要性质：

若 \(i < j\)，则 \(e_i \le e_j\)
在考虑第 \(i\) 个活动时，所有可能不冲突的活动一定来自区间 \([1, i-1]\)

这是后续二分查找与 DP 的基础。

三、DP 状态设计

状态定义

设排序后的活动编号为 \(1 \sim n\)。

定义： \[ f(j, i) = \text{在前 } i \text{ 个活动中，最多选择 } j \text{ 个活动所能获得的最大价值} \] 其中：

\(0 \le j \le k\)
\(0 \le i \le n\)
边界：\(f(0, i) = 0\)，\(f(j, 0) = 0\)

四、状态转移方程

考虑第 \(i\) 个活动（排序后）：

1. 不选第 \(i\) 个活动

\[ f(j, i) = f(j, i-1) \]

2. 选第 \(i\) 个活动

需要找到最后一个 不与第 \(i\) 个活动冲突 的活动位置。

定义： \[ pre[i] = \max \{ t \mid t < i \ \text{且} \ e_t < s_i \} \] 则若选择第 \(i\) 个活动： \[ f(j, i) = f(j-1, pre[i]) + v_i \]

综合转移

\[ f(j, i) = \max \big( f(j, i-1),\ f(j-1, pre[i]) + v_i \big) \]

五、`pre[i]` 的计算：二分查找

由于活动已按结束时间排序，数组 \(e_1, e_2, \dots, e_n\) 单调不减。

因此，对每个活动 \(i\)，可以在区间 \([1, i-1]\) 上二分查找最大的下标 \(t\)，使得： \[ e_t < s_i \] 时间复杂度为 \(O(\log n)\)，所有 \(pre[i]\) 可在 \(O(n \log n)\) 内预处理完成。

六、空间优化：滚动数组

注意到状态转移中：

\(f(j, i)\) 只依赖于
- 当前行 \(f(j, i-1)\)
- 上一行 \(f(j-1, pre[i])\)

因此无需保留完整的二维 DP 表，只需保留两行即可。

令：

f[0][i] 表示上一层 \(j-1\)
f[1][i] 表示当前层 \(j\)

通过 j & 1 实现滚动。

七、时间与空间复杂度

排序：\(O(n \log n)\)
预处理 pre：\(O(n \log n)\)
DP 转移：\(O(k \cdot n)\)

在题目约束 \(k \cdot n \le 10^6\) 下完全可行。

空间复杂度：\(O(n)\)

八、AC代码

class Solution {
public:
    // 比较器：按结束时间升序，结束时间相同则按开始时间升序
    struct cmp {
        bool operator()(vector<int>& a, vector<int>& b) {
            if (a[1] != b[1])
                return a[1] < b[1];
            return a[0] < b[0];
        }
    };

    // 在前 i-1 个活动中，找到最后一个满足 end < k 的位置
    // 返回的是“数量意义上的下标”，范围为 [0, i-1]
    int search(int k, int i, vector<vector<int>>& events) {
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (events[mid - 1][1] < k)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }

    int maxValue(vector<vector<int>>& events, int k) {
        // 1. 按结束时间排序
        sort(events.begin(), events.end(), cmp());

        int n = events.size();

        // f[2][i]：滚动数组，表示 DP 的当前行和上一行
        vector<vector<int>> f(2, vector<int>(n + 1));

        // pre[i]：第 i 个活动对应的最后一个不冲突活动位置
        vector<int> pre(n + 1);

        // 2. 预处理 pre 数组
        for (int i = 1; i <= n; ++i) {
            pre[i] = search(events[i - 1][0], i, events);
        }

        // 3. 动态规划
        for (int j = 1; j <= k; ++j) {
            f[j & 1][0] = 0;  // 前 0 个活动，价值为 0
            for (int i = 1; i <= n; ++i) {
                // 不选第 i 个活动
                f[j & 1][i] = f[j & 1][i - 1];

                // 选第 i 个活动
                f[j & 1][i] = max(
                    f[j & 1][i],
                    f[(j - 1) & 1][pre[i]] + events[i - 1][2]
                );
            }
        }

        // 4. 最终答案
        return f[k & 1][n];
    }
};

九、总结

该问题的核心在于：

按结束时间排序，保证二分查找合法性
通过 pre[i] 将区间不重叠约束转化为 DP 索引
使用滚动数组将空间复杂度从 \(O(kn)\) 降为 \(O(n)\)

这是一个标准且高效的「区间 DP + 二分优化」模型，适用于一类“带数量限制的区间选择问题”。

考点

思路