题目描述
给你一个 events
数组,其中 events[i] = [startDay_i, endDay_i, value_i]
,表示第 i
个会议在 startDay_i
天开始,第 endDay_i
天结束,如果你参加这个会议,你能得到价值 value_i
。同时给定一个整数 k
表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议,那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的,也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
返回能得到的会议价值 最大和。
样例
输入:events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出:7
解释:选择绿色的活动会议 0 和 1,得到总价值和为 4 + 3 = 7 。
输入:events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出:10
解释:参加会议 2 ,得到价值和为 10 。
你没法再参加别的会议了,因为跟会议 2 有重叠。你不需要参加满 k 个会议。
输入: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
算法
(动态规划) $O(nk \log n)$
- 对所有会议按照结束时间从小到大排序。
- 设状态 $f(i, j)$ 表示前 $i$ 个会议中,最多参加 $j$ 场会议的最大收益。$i$ 下标从 1 开始。
- 初始时,所有状态为 0。
- 对于会议 $i$,通过二分查询找到最大的会议编号 $l$,满足会议 $j$ 的结束时间小于会议 $i$ 的开始时间。此时对于 $f(i, j)$ 有三种转移:
- 忽视第 $i$ 场会议,从 $f(i - 1, j)$ 转移。
- 参加这一场会议,从 $f(l, j - 1)$ 转移。
- 最终答案为 $f(n, k)$。
时间复杂度
- 初始化排序的时间为 $O(n \log n)$。
- 动态规划状态数为 $O(nk)$,转移需要 $O(\log n)$ 的时间。
- 故总时间复杂度为 $O(nk \log n)$。
空间复杂度
- 需要 $O(nk)$ 的空间存储动态规划的状态。
C++ 代码
#define LL long long
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
const int n = events.size();
sort(events.begin(), events.end(),
[](const vector<int> &a, const vector<int> &b) {
return a[1] < b[1];
});
events.insert(events.begin(), vector<int>{0, 0, 0});
vector<vector<LL>> f(n + 1, vector<LL>(k + 1, 0));
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
int l = 0, r = i - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (events[mid + 1][1] >= events[i][0]) r = mid;
else l = mid + 1;
}
f[i][0] = 0;
for (int j = 1; j <= k; j++)
f[i][j] = max(f[i - 1][j], f[l][j - 1] + events[i][2]);
}
return f[n][k];
}
};
对于会议 i,通过二分查询找到最大的会议编号 l,满足会议 j 的结束时间小于会议 i 的开始时间。
有一个小小的问题是为什么只转移最大的会议编号 l,理论上来讲,l之前的会议也都可以转移过来
f(l,j−1)并不一定是 f(k,j-1) k <= l 当中最大的
因为每次转移都有不参加当前会议的选择,所以 $f(l, j - 1)$ 一定是前缀中最优的
好的 明白了 谢谢大佬
咋想到要添加哨兵的啊
方便处理,不加也可以,但特判就比较麻烦