【面试高频题】难度 2/5，结合二分的序列 DP 运用题
【面试高频题】难度 2/5，结合二分的序列 DP 运用题
题目描述
这是 LeetCode 上的「1751. 最多可以参加的会议数目 II」，难度为「困难」。
Tag : 「二分」、「序列 DP」
给你一个 events 数组，其中 events[i] = [startDay_i, endDay_i, value_i] ，表示第 i 个会议在 startDay_i 天开始，第 endDay_i 天结束，如果你参加这个会议，你能得到价值 value_i 。
同时给你一个整数 k 表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须完整地参加完这个会议。
会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值最大和。
示例 1：
输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。
示例 2：
输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。
示例 3：
输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。
提示：
- 1 <= k <= events.length
- 1 <= k * events.length <= 10^6
- 1 <= startDay_i <= endDay_i <= 10^9
- 1 <= value_i <= 10^6
基本思路
定义 f[i][j] 为考虑前 i 个事件，选择不超过 j 的最大价值。
对于每个事件，都有选择与不选两种选择：
- 不选：f[i][j] = f[i - 1][j]
- 选：找到第 i 件事件之前，与第 i 件事件不冲突的事件，记为
last，则有f[i][j] = f[last][j - 1] + value_i 两者取 max ，则是 f[i][j] 的值。
分析到这里，因为我们要找 last，我们需要先对 events 的结束时间排序，然后找从右往左找，找到第一个满足 结束时间 小于 当前事件的开始时间 的事件，就是 last
而找 last 的过程，可以直接循环找，也可以通过二分来找，都能过。
动态规划
不通过「二分」来找 last 的 DP 解法。
代码：
class Solution {
public int maxValue(int[][] es, int k) {
int n = es.length;
Arrays.sort(es, (a, b)->a[1]-b[1]);
// f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
int[][] f = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
int[] ev = es[i - 1];
int s = ev[0], e = ev[1], v = ev[2];
// 找到第 i 件事件之前，与第 i 件事件不冲突的事件
// 对于当前事件而言，冲突与否，与 j 无关
int last = 0;
for (int p = i - 1; p >= 1; p--) {
int[] prev = es[p - 1];
if (prev[1] < s) {
last = p;
break;
}
}
for (int j = 1; j <= k; j++) {
f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);
}
}
return f[n][k];
}
}
- 时间复杂度：排序复杂度为 O(n\log{n}) ，循环
n个事件，每次循环需要往回找一个事件，复杂度为 O(n) ，并更新k个状态，复杂度为 O(k) ，因此转移的复杂度为 O(n * (n + k)) ；总的复杂度为O(n * (n + k + \log{n})) - 空间复杂度：O(n * k)
二分 + 动态规划
通过「二分」来找 last 的 DP 解法。
代码：
class Solution {
public int maxValue(int[][] es, int k) {
int n = es.length;
Arrays.sort(es, (a, b)->a[1]-b[1]);
// f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
int[][] f = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
int[] ev = es[i - 1];
int s = ev[0], e = ev[1], v = ev[2];
// 通过「二分」，找到第 i 件事件之前，与第 i 件事件不冲突的事件
// 对于当前事件而言，冲突与否，与 j 无关
int l = 1, r = i - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
int[] prev = es[mid - 1];
if (prev[1] < s) l = mid;
else r = mid - 1;
}
int last = (r > 0 && es[r - 1][1] < s) ? r : 0;
for (int j = 1; j <= k; j++) {
f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);
}
}
return f[n][k];
}
}
- 时间复杂度：排序复杂度为 O(n\log{n}) ，循环
n个事件，每次循环需要往回找一个事件，复杂度为 O(\log{n}) ，并更新k个状态，复杂度为 O(k) ，因此转移的复杂度为 O(n * (\log{n} + k)) ；总的复杂度为O(n * (k + \log{n})) - 空间复杂度：O(n * k)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1751 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
