给你一个 events
数组,其中 events[i] = [startDayi, endDayi, valuei]
,表示第 i
个会议在 startDayi
天开始,第 endDayi
天结束,如果你参加这个会议,你能得到价值 valuei
。同时给你一个整数 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 <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106
方法一:记忆化搜索 + 二分查找
我们先将会议按照开始时间从小到大排序,然后设计一个函数
函数
对于第
其中
由于函数
时间复杂度
方法二:动态规划 + 二分查找
我们可以将方法一中的记忆化搜索改为动态规划。
先将会议排序,这次我们按照结束时间从小到大排序。然后定义
对于第
其中
时间复杂度
相似题目:
class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
@cache
def dfs(i, k):
if i >= len(events):
return 0
_, e, v = events[i]
ans = dfs(i + 1, k)
if k:
j = bisect_right(events, e, lo=i+1, key=lambda x: x[0])
ans = max(ans, dfs(j, k - 1) + v)
return ans
events.sort()
return dfs(0, k)
class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
events.sort(key=lambda x: x[1])
n = len(events)
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i, (s, _, v) in enumerate(events):
h = bisect_left(events, s, hi=i, key=lambda x: x[1])
for j in range(1, k + 1):
dp[i + 1][j] = max(dp[i][j], dp[h][j - 1] + v)
return dp[n][k]
class Solution {
private int[][] events;
private int[][] f;
private int n;
public int maxValue(int[][] events, int k) {
Arrays.sort(events, (a, b) -> a[0] - b[0]);
this.events = events;
n = events.length;
f = new int[n][k + 1];
return dfs(0, k);
}
private int dfs(int i, int k) {
if (i >= n || k <= 0) {
return 0;
}
if (f[i][k] != 0) {
return f[i][k];
}
int j = search(events, events[i][1], i + 1);
int ans = Math.max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);
f[i][k] = ans;
return ans;
}
private int search(int[][] events, int x, int i) {
int left = i, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (events[mid][0] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
int n = events.length;
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i < n; ++i) {
int s = events[i][0], v = events[i][2];
int h = search(events, s, i);
for (int j = 1; j <= k; ++j) {
dp[i + 1][j] = Math.max(dp[i][j], dp[h][j - 1] + v);
}
}
return dp[n][k];
}
private int search(int[][] events, int x, int n) {
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (events[mid][1] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
sort(events.begin(), events.end());
int n = events.size();
vector<vector<int>> f(n, vector<int>(k + 1));
function<int(int, int)> dfs = [&](int i, int k) -> int {
if (i >= n || k <= 0) return 0;
if (f[i][k]) return f[i][k];
vector<int> t = {events[i][1]};
int j = upper_bound(events.begin() + i + 1, events.end(), t, [&](auto& l, auto& r) -> bool { return l[0] < r[0]; }) - events.begin();
int ans = max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);
f[i][k] = ans;
return ans;
};
return dfs(0, k);
}
};
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
sort(events.begin(), events.end(), [&](auto& l, auto& r) -> bool { return l[1] < r[1]; });
int n = events.size();
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
for (int i = 0; i < n; ++i) {
int s = events[i][0], v = events[i][2];
int h = lower_bound(events.begin(), events.begin() + i, s, [](auto& e, int x) { return e[1] < x; }) - events.begin();
for (int j = 1; j <= k; ++j) {
dp[i + 1][j] = max(dp[i][j], dp[h][j - 1] + v);
}
}
return dp[n][k];
}
};
func maxValue(events [][]int, k int) int {
sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] })
n := len(events)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, k+1)
}
var dfs func(i, k int) int
dfs = func(i, k int) int {
if i >= n || k <= 0 {
return 0
}
if f[i][k] > 0 {
return f[i][k]
}
j := sort.Search(n, func(h int) bool { return events[h][0] > events[i][1] })
ans := max(dfs(i+1, k), dfs(j, k-1)+events[i][2])
f[i][k] = ans
return ans
}
return dfs(0, k)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func maxValue(events [][]int, k int) int {
sort.Slice(events, func(i, j int) bool { return events[i][1] < events[j][1] })
n := len(events)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, k+1)
}
for i, event := range events {
h := sort.Search(i, func(k int) bool { return events[k][1] >= event[0] })
for j := 1; j <= k; j++ {
dp[i+1][j] = max(dp[i][j], dp[h][j-1]+event[2])
}
}
return dp[n][k]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}