题目描述
思路解析
一句话答案：LeetCode 2054 两个最好的不重叠活动：等号也算重叠。按开始时间排序后能接的搭档是一段后缀，倒着填后缀最大值 f，逐活动二分找开始严格大于结束的边界配对取最大。时间 O(n log n)、空间 O(n)。
结束于 5、开始于 5，凭什么也算重叠
每个活动给三个数：开始、结束、价值。最多挑两个参加，求价值之和最大，只挑一个也行。规则里埋着一个等号：开始和结束两个时刻都算占用——结束于 5、另一个从 5 开始，就在时刻 5 撞上，后者至少从 6 开始才接得上。写成条件就是后一个的开始必须严格大于前一个的结束，差一个等号，合法性完全两样。
活动两两硬配，为什么 n 一大就试不完
n 个活动两两配成对约有 n²/2 种，几万个活动就是十亿量级，逐对查重叠、算价值和，跑不完（O(n²)，大 O 描述数据量变大时操作次数怎么涨）。慢的根子是同一个数被重算了 n 遍：固定一个活动后，真正想知道的只有一件事——在它结束之后才开始的那批活动里，最大价值是多少。提前存好就省了。
f 这一列为什么要从最后一行倒着填
先按开始时间从小到大排序，把排序后的活动列成表、一行一个活动。某个活动的开始一旦大于我的结束，排它后面的活动也都大于——能接上的搭档连成一段尾巴。尾巴里只关心价值最高的那个，于是定义后缀最大值 f[i]（从第 i 行起到最后一行，价值最大是多少）。
这是一小段动态规划（先把『第 i 行往下价值最高是多少』逐行填好，配对时直接查）：f[i]=max(f[i+1], 本行价值)，每格依赖下一格，只能从最后一行倒着往上填，最后一行的 f 就是它自己的价值。
每个活动的搭档，为什么二分一次就锁定
『开始大于我的结束』在排好的数组里从某一行起整段成立，一刀切的分界正适合二分（每次看中间那行、一半一半排除的查找法），找出第一个开始严格大于当前结束的下标 idx，f[idx] 加本活动价值就是以它打头的最好组合。idx 越界说明谁都接不上，本活动单独参加，裸价值也参与取最大，『只选一个』就这么算进去了。
拿题面三个活动，亲手把 4 算出来
用题面第一组 events=[[1,3,2],[4,5,2],[2,4,3]]。按开始排序得 [[1,3,2],[2,4,3],[4,5,2]]。倒着填 f（下标从 0 数起）：f[2]=2；f[1]=max(2,3)=3；f[0]=max(3,2)=3，f=[3,3,2]。
逐个配对：[1,3,2] 结束于 3，第一个开始大于 3 的是下标 2 的 [4,5,2]，得 2+f[2]=2+2=4；[2,4,3] 结束于 4，下标 2 的开始是 4，不严格大于 4，接不上，单独算 3；[4,5,2] 结束于 5，后面没人，单独算 2。候选 4、3、2 取最大，答案 4，题面给的也是 4。
边界写成大于等于，5 分为什么会冒出来
二分条件一旦写成大于等于，[2,4,3] 就会接上开始于 4 的 [4,5,2]，得 3+2=5——多出的 1 分来自时刻 4 被占两次的非法组合。f 的方向也别弄错，f[i] 靠 f[i+1] 推，从上往下填拿到的全是没算好的值；二分还依赖排序，没排就没有整段分界可找。
排序 O(n log n) 是大头，填 f 一趟 O(n)，逐活动二分共 O(n log n)，合计 O(n log n)；额外一列 f，空间 O(n)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套:排序,填后缀最大值 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题