1751. 最多可以参加的会议数目 II - 力扣（LeetCode）
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
// 特判 k=1 的情况
if (k == 1) {
return ranges::max(events, {}, [](auto& e) { return e[2]; })[2];
} // 1. 使用 ranges::sort 按结束时间排序
ranges::sort(events, {}, [](auto& e) { return e[1]; }); int n = events.size();
// f[i][j] 表示考虑前 i 个事件，最多参加 j 个会议的最大价值
vector f(n + 1, vector<int>(k + 1, 0)); for (int i = 0; i < n; i++) {
// 2. 使用 ranges::lower_bound 替换传统的 lower_bound
// views::take(i) 创建一个仅包含前 i 个元素的视图
// 投影 [](auto& e) { return e[1]; } 提取结束时间进行比较
auto it = ranges::lower_bound(events | views::take(i), events[i][0], {}, [](auto& e) {
return e[1];
});
int p = distance(events.begin(), it); for (int j = 1; j <= k; j++) {
f[i + 1][j] = max(f[i][j], f[p][j - 1] + events[i][2]);
}
}
return f[n][k];
}
};
1. 核心算法：动态规划 (DP) + 二分查找
该题是经典的加权区间调度问题。由于可以参加 $k$ 个会议，我们不能简单地只记录一个最大值，而是需要维护一个二维状态。
DP 状态定义
$f[i][j]$：表示考虑前 $i$ 个事件，且最多参加 $j$ 个会议时能获得的最大价值。
DP 转移方程
对于当前第 $i$ 个事件（索引为 $i$，但在 DP 表中对应 $i+1$）：
- 不参加：价值等于前 $i-1$ 个事件参加 $j$ 个会议的价值：$f[i][j]$。
- 参加：价值等于“上一个不重叠事件”状态下的最大价值 + 当前事件价值：$f[p][j-1] + events[i][2]$。
- 其中 $p$ 是通过二分查找得到的索引，满足 $events[p].end < events[i].start$。
$$f[i+1][j] = \max(f[i][j], f[p][j-1] + \text{value}_i)$$
2. 代码逻辑解析
A. 预处理与排序
ranges::sort(events, {}, [](auto& e) { return e[1]; });
按结束时间排序是区间 DP 的标准做法。它保证了当我们处理第 $i$ 个事件时，所有可能与之匹配的“前一个事件”都在它的左侧。
B. 二分查找定位
auto it = ranges::lower_bound(events | views::take(i), events[i][0], {}, [](auto& e) {return e[1];
});
int p = distance(events.begin(), it);
- 这里寻找的是第一个结束时间 $\ge$ 当前开始时间的位置。
- 因为
f[p]在定义上对应的是前p个事件，所以二分返回的索引p恰好可以直接作为f数组的第一维下标。
C. 二维 DP 填表
for (int j = 1; j <= k; j++) {f[i + 1][j] = max(f[i][j], f[p][j - 1] + events[i][2]);
}
- 外层循环遍历事件，内层循环遍历允许参加的会议数 $k$。
- 这种写法通过 $O(N \cdot K)$ 的复杂度完成了状态转移。
3. 复杂度分析
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | $O(N \log N + N \cdot K)$ | 排序 $O(N \log N)$，外层循环 $N$ 次，内层二分 $O(\log N)$，转移 $O(K)$。 |
| 空间复杂度 | $O(N \cdot K)$ | 存储二维 DP 数组所需的空间。 |
4. 现代 C++ (C++20) 特性亮点
这段代码使用了 C++20 的高性能特性，使代码非常简洁：
std::ranges::sort：不再需要begin()和end()。std::views::take(i)：创建了一个轻量级视图，限制二分查找的范围仅在当前元素之前，增强了安全性。- 投影 (Projections)：在
sort和lower_bound中直接传入[](auto& e) { return e[1]; }，无需手动解引用复杂的迭代器。 - CTAD (Class Template Argument Deduction)：
vector f(n + 1, ...)自动推导 vector 类型。