LeetCode 题解工作台
最多可以参加的会议数目 II
给你一个 events 数组，其中 events[i] = [startDay i , endDay i , value i ] ，表示第 i 个会议在 startDay i 天开始，第 endDay i 天结束，如果你参加这个会议，你能得到价值 value i 。同时给你一个整数 k 表示你能参加…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们先将会议按照开始时间从小到大排序，然后设计一个函数 $\text{dfs}(i, k)$ 表示从第 个会议开始，最多参加 个会议的最大价值和。答案即为 $\text{dfs}(0, k)$。 函数 $\text{dfs}(i, k)$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 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.length1 <= k * events.length <= 1061 <= startDayi <= endDayi <= 1091 <= valuei <= 106
解题思路
方法一：记忆化搜索 + 二分查找
我们先将会议按照开始时间从小到大排序，然后设计一个函数 表示从第 个会议开始，最多参加 个会议的最大价值和。答案即为 。
函数 的计算过程如下：
如果不参加第 个会议，那么最大价值和就是 ；如果参加第 个会议，我们可以通过二分查找，找到第一个开始时间大于第 个会议结束时间的会议，记为 ，那么最大价值和就是 。取二者的较大值即可。即：
其中 为第一个开始时间大于第 个会议结束时间的会议，可以通过二分查找得到。
由于函数 的计算过程中，会调用 和 ，因此我们可以使用记忆化搜索，将计算过的值保存下来，避免重复计算。
时间复杂度 ，空间复杂度 ，其中 为会议数量。
class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
@cache
def dfs(i: int, k: int) -> int:
if i >= len(events):
return 0
_, ed, val = events[i]
ans = dfs(i + 1, k)
if k:
j = bisect_right(events, ed, lo=i + 1, key=lambda x: x[0])
ans = max(ans, dfs(j, k - 1) + val)
return ans
events.sort()
return dfs(0, k)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * (k + log n)) because for each event and each possible attended count up to k, binary search is performed to find the next compatible event. Space complexity is O(n * k) to store the DP table for state transitions. |
| 空间 | O(n \cdot k) |
面试官常问的追问
外企场景- question_mark
They may ask about handling overlapping events efficiently using binary search after sorting.
- question_mark
Expect questions on optimizing DP transitions for large n * k to avoid timeouts.
- question_mark
Clarify why attending fewer than k events may be optimal if higher-value events overlap.
常见陷阱
外企场景- error
Forgetting that end days are inclusive, which causes overlaps if not handled carefully.
- error
Not sorting events before binary search, leading to incorrect next-event selection.
- error
Assuming you must attend exactly k events instead of at most k, which can reduce total value.
进阶变体
外企场景- arrow_right_alt
Modify to return the actual sequence of events that maximizes value, not just the sum.
- arrow_right_alt
Change k to be dynamic per event, allowing variable attendance limits.
- arrow_right_alt
Introduce additional constraints such as minimum rest days between events.