LeetCode 题解工作台
最多可以参加的会议数目
给你一个数组 events ，其中 events[i] = [startDay i , endDay i ] ，表示会议 i 开始于 startDay i ，结束于 endDay i 。 你可以在满足 startDay i i 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。 …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们用一个哈希表 记录每个会议的开始和结束时间。键为会议的开始时间，值为一个列表，包含所有在该开始时间开始的会议的结束时间。用两个变量 和 分别记录会议的最小开始时间和最大结束时间。 对于从小到大每个在 到 的时间点 ，我们需要做以下操作：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。
请你返回你可以参加的 最大 会议数目。
示例 1：
输入：events = [[1,2],[2,3],[3,4]] 输出：3 解释：你可以参加所有的三个会议。 安排会议的一种方案如上图。 第 1 天参加第一个会议。 第 2 天参加第二个会议。 第 3 天参加第三个会议。
示例 2：
输入：events= [[1,2],[2,3],[3,4],[1,2]] 输出：4
提示：
1 <= events.length <= 105events[i].length == 21 <= startDayi <= endDayi <= 105
解题思路
方法一：哈希表 + 贪心 + 优先队列
我们用一个哈希表 记录每个会议的开始和结束时间。键为会议的开始时间，值为一个列表，包含所有在该开始时间开始的会议的结束时间。用两个变量 和 分别记录会议的最小开始时间和最大结束时间。
对于从小到大每个在 到 的时间点 ，我们需要做以下操作：
- 从优先队列中移除所有结束时间小于当前时间 的会议。
- 将所有开始时间等于当前时间 的会议的结束时间加入优先队列中。
- 如果优先队列不为空，则取出结束时间最小的会议，累加答案数，并从优先队列中移除该会议。
这样，我们可以确保在每个时间点 ，我们都能参加结束时间最早的会议，从而最大化参加的会议数。
时间复杂度 ，空间复杂度 ，其中 和 分别为会议的最大结束时间和会议的数量。
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
g = defaultdict(list)
l, r = inf, 0
for s, e in events:
g[s].append(e)
l = min(l, s)
r = max(r, e)
pq = []
ans = 0
for s in range(l, r + 1):
while pq and pq[0] < s:
heappop(pq)
for e in g[s]:
heappush(pq, e)
if pq:
heappop(pq)
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O((T + n) \log n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for knowledge of greedy algorithms and sorting.
- question_mark
Test the candidate's ability to implement sorting and iterate efficiently.
- question_mark
Assess how the candidate handles edge cases with overlapping events.
常见陷阱
外企场景- error
Failing to account for tie-breaking when sorting events by end day.
- error
Not implementing the greedy strategy properly by picking conflicting events.
- error
Overlooking edge cases such as overlapping events with the same start and end day.
进阶变体
外企场景- arrow_right_alt
What if you had to maximize the events attended within a specific time range?
- arrow_right_alt
How would the problem change if events had durations instead of start and end days?
- arrow_right_alt
What if there were multiple event categories, and each category had a separate maximum number of events?