题目描述
思路解析动画文字版
记牢这套:排序,填后缀最大值 f,再逐个活动找第一个开得下的边界、用本价值加边界处的 f。下面按这套一步步填表。
输入 · 五个活动,开始时间乱序：先把五个活动摊成一张表,每一行是一个活动,列从左到右是开始、结束、价值,右边两列 f 和配对是我们待会儿要算的辅助值,现在先空着。左边那一列是活动的名字 A 到 E。你看开始时间这一列是 3,1,6,2,4,乱的,第一步得把它排好。
排序 · 按开始时间从小到大：按开始时间从小到大排一遍。现在左边活动名的顺序变成了 B、D、A、E、C,开始时间这一列(绿色)是 1、2、3、4、6,规规矩矩升序。排序这一步很关键:排好之后,只要某个活动的开始时间大于我的结束时间,它以及它下面所有活动的开始时间都大于我的结束,天然接得上,后面找边界才能一刀切。
看两列辅助值 · f 与配对：正式开算前,先说清右边两列是干嘛的。f 这一列,表示从这一行往下、价值最高的活动值多少,它帮我们一眼看出结束之后能接的最好活动。配对这一列,是把本活动价值,加上它结束后能接的那个最优价值,得到以这个活动打头的最好组合。两列都从下往上、从上往下分两趟填,先填 f。
填后缀最大值 · 活动 C 的 f = 6：从最后一行活动 C 开始填 f。它下面没有别人了,所以从它往下价值最大的就是它自己,f 记成它的价值 6。
填后缀最大值 · 活动 E 的 f = 6：往上填活动 E 这一行的 f。比较两个数:下面一行的 f 是 6,本行自己的价值是 3,谁大取谁,f = 6。下面已经有更高价值的活动,f 沿用 6。
填后缀最大值 · 活动 A 的 f = 7：往上填活动 A 这一行的 f。比较两个数:下面一行的 f 是 6,本行自己的价值是 7,谁大取谁,f = 7。本行价值更大,f 被自己刷新了。
填后缀最大值 · 活动 D 的 f = 7：往上填活动 D 这一行的 f。比较两个数:下面一行的 f 是 7,本行自己的价值是 5,谁大取谁,f = 7。下面已经有更高价值的活动,f 沿用 7。
填后缀最大值 · 活动 B 的 f = 7：往上填活动 B 这一行的 f。比较两个数:下面一行的 f 是 7,本行自己的价值是 4,谁大取谁,f = 7。下面已经有更高价值的活动,f 沿用 7。
f 列填完 · 每行往下的最大价值：f 这一列填完了,从上到下是 7、7、7、6、6。它的含义再强调一遍:比如第四行 E 的 f 是 6,意思是从 E 往下(也就是 E 和 C 里)价值最高的是 6。有了这一列,任何活动只要知道结束后从哪一行接得上,就能立刻查出那之后能拿的最高价值。接下来逐个活动算配对。
找边界 · 活动 B 之后能接谁：轮到活动 B 当打头的,它结束于 2。往下找第一个开始时间严格大于 2 的活动,是活动 A,它的开始是 3(紫色是本活动结束,黄色是接得上的分界)。从这一行往下的活动都不会和 B 撞。
结算配对 · 活动 B = 11：接得上就好办了。从分界那一行往下最高价值就是那行的 f,等于 7。用 B 自己的价值 4 加上 7,配对总价值是 11(绿色),记到配对列。目前所有配对里最大的是 11。
找边界 · 活动 D 之后能接谁：轮到活动 D 当打头的,它结束于 4。往下找第一个开始时间严格大于 4 的活动,是活动 C,它的开始是 6(紫色是本活动结束,黄色是接得上的分界)。从这一行往下的活动都不会和 D 撞。
结算配对 · 活动 D = 11：接得上就好办了。从分界那一行往下最高价值就是那行的 f,等于 6。用 D 自己的价值 5 加上 6,配对总价值是 11(绿色),记到配对列。目前所有配对里最大的是 11。
找边界 · 活动 A 之后能接谁：轮到活动 A 当打头的,它结束于 5。往下找第一个开始时间严格大于 5 的活动,是活动 C,它的开始是 6(紫色是本活动结束,黄色是接得上的分界)。从这一行往下的活动都不会和 A 撞。
结算配对 · 活动 A = 13：接得上就好办了。从分界那一行往下最高价值就是那行的 f,等于 6。用 A 自己的价值 7 加上 6,配对总价值是 13(绿色),记到配对列。目前所有配对里最大的是 13。
找边界 · 活动 E 之后能接谁：轮到活动 E 当打头的,它结束于 6。可它已经排在很后面,下面再没有哪个活动的开始时间大于 6 了,谁都接不上。那它只能单独参加。
结算配对 · 活动 E = 3：接不上,活动 E 只能自己参加,配对总价值就是它自己的价值 3(绿色)。目前所有配对里最大的仍是 13。
找边界 · 活动 C 之后能接谁：轮到活动 C 当打头的,它结束于 7。可它已经排在很后面,下面再没有哪个活动的开始时间大于 7 了,谁都接不上。那它只能单独参加。
结算配对 · 活动 C = 6：接不上,活动 C 只能自己参加,配对总价值就是它自己的价值 6(绿色)。目前所有配对里最大的仍是 13。
取最大 · 配对列里最高的就是答案：五个活动的配对都算完了,配对这一列从上到下是 11、11、13、3、6。里头最大的是 13,出现在活动 A 那一行(绿色)。这个 13 就是最终答案。
回放 · 最优的两个活动：把这个 13 拆开看是谁凑的。打头的是活动 A,开始 3 结束 5,价值 7;它结束于 5,接上开始于 6 的活动 C,价值 6。两段时间不碰,价值 7 加 6 等于 13,这就是最优组合。
边界想清:重叠的大活动要退而选能接的组合、单独一个大活动可能就是最优、结束加一等于下一个开始时严格大于成立可同选。
面试重点:排序加后缀最大值 f 加二分找边界、可换扫描线加堆、单独参加已含在配对里。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxTwoEvents(self, events: List[List[int]]) -> int: events.sort() n = len(events) f = [events[-1][2]] * n for i in range(n - 2, -1, -1): f[i] = max(f[i + 1], events[i][2]) ans = 0 for _, e, v in events: idx = bisect_right(events, e, key=lambda x: x[0]) if idx < n: v += f[idx] ans = max(ans, v) return ans复杂度
- 时间：O(n log n)，排序是 O(n log n),是主导项。填后缀最大值 f 扫一遍是 O(n)。之后枚举每个活动、各做一次二分找边界,是 O(n log n)。合起来 O(n log n)
- 空间：O(n)，按峰值算。额外开了一列长度约 n 的后缀最大值数组 f,所以是 O(n)。排序本身的额外开销三语言不同,但都不超过这一列的量级
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问除了排序加二分,还有别的解法吗?
追问为什么答案里只选一个活动的情况不会漏?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
喂食仓鼠的最小食物桶数
LeetCode 2086 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题