题目描述
思路解析
一句话答案：LeetCode 1235 规划兼职工作用排序加 DP 加二分：工作按结束时间排好，dp[i] 记前 i 份最大收益，每份在「不接」与「接它加二分找到的前驱」之间取大，时间 O(n log n)、空间 O(n)。
规划兼职工作到底在挑哪几份
给三个等长数组 startTime、endTime、profit，第 i 份工作占区间 [开始, 结束)（右端不含：上一份结束正好等于下一份开始，不算重叠）、做完拿 profit[i]。挑若干份、时间互不重叠，让收益之和最大。题面 start=[1,2,3,3]、end=[3,4,5,6]、profit=[50,10,40,70]，答案 120。
为什么挨个试选或不选会爆
每份工作都有「选」「不选」两条岔路，n 份就有 2ⁿ 种组合，逐一验重叠求和，n 一大数不完，且组合前半截大量重合被反复重算。把「前面若干份的最优收益」记下来复用就省了——这就是动态规划（DP，把前若干份工作的最大报酬记表、后面直接取）。
按结束时间排序，dp[i] 到底存什么
先把工作按结束时间从小到大排好，本例得结束 = [3,4,5,6]、开始 = [1,2,3,3]、收益 = [50,10,40,70]。排好后，任一份工作「能接在前面的那批」必是连续的一段前缀（前缀=最靠前的一段），才好用二分（在有序数据里对半砍、快速定位的查法）切出来。据此定义 dp[i]：前 i 份、不重叠时能拿的最大收益。dp[0] = 0：没考虑任何工作。
接一份工作，前驱该从哪一格接
填 dp[i] 时，第 i 份只有两条路。不接它，收益沿用 dp[i-1]。接它，就先找前面「结束时间 ≤ 它的开始时间」的工作，份数记作 j，用二分找结束时间里「第一个大于当前开始时间的位置」，那个下标就是 j。
前 j 份的最优收益存在 dp[j] 里，接上加本份 profit 就是「接这份」的收益。两条取大，转移（由已算好的格子推出当前格的式子）即 dp[i] = max(dp[i-1], dp[j] + profit)。
拿题面四份工作把表填出来
接上一节排好的顺序填表，dp[0] = 0。前两份开始 1、2。第 1 份最靠前、没有前驱；第 2 份开始 2，排在它前面的只有第 1 份、结束在 3，3 > 2 接不上，两份都只能单干：dp[1] = 50；第 2 份自身 10 不如沿用，dp[2] = 50。第 3 份开始 3、收益 40，结束 ≤ 3 有 1 份，接 dp[1] 得 90 胜过 50，dp[3] = 90。第 4 份开始 3、收益 70，结束 ≤ 3 有 1 份，接 dp[1] 得 120 胜过 90，dp[4] = 120。
二分边界写成 <，正好接得上的那份为什么会丢
把二分等号写丢——用「结束时间 < 开始时间」找前驱，第 3 份卡在 3 = 3 的工作被排除，dp[4] 接不到 dp[1]，120 缩水成 90，题面明明写着结束等于开始算可接，代码就得用 ≤。另一处是排序键：必按结束时间排，可接工作才凑成能二分的前缀，错按开始或收益排就失效。
排序花 O(n log n)（大 O 记号描述数据规模变大时操作数怎么涨），之后填 n 格、每格一次二分是 O(log n)，合起来仍是 O(n log n)，对 n 到 5 万完全够用；dp 与结束时间数组都是 O(n) 空间。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句口诀:dp[i] = max( 不接(dp[i-1]) , 接它(dp[二分位置] + 本份收益) )。下面每填一格都在套它。
第一步,把四份工作按结束时间升序排好,得到结束 = [3,4,5,6]、开始 = [1,2,3,3]、收益 = [50,10,40,70]。排序的好处是:任何一份工作能配的「前面那批」一定是排序后连续的前缀,这样才好用二分去切。
dp 第 0 格固定是 0:还没考虑任何工作,收益自然是 0。绿色这一格是后面所有计算的地基。
现在要填 dp[1]。当前这份工作开始 1、结束 3、收益 50。它有两条路:不接它,或者接它。先看接它能配上谁。
接它的话,前面只能配「结束时间 ≤ 它的开始时间 1」的工作。在已排好的结束时间上二分,数出这样的工作有 0 份(一份都没有,它开始得太早)。这 0 份的最优组合正是 dp[0](蓝色)。
两条路算清楚:不接这份,收益沿用 dp[0] = 0;接这份,收益是它配上 dp[0] = 0,再加自己的 50,得 50。接它更高,选 50。
第 1 格结算:dp[1] = 50(绿色锁定)。后面更晚结束的工作会接着用它。
现在要填 dp[2]。当前这份工作开始 2、结束 4、收益 10。它有两条路:不接它,或者接它。先看接它能配上谁。
接它的话,前面只能配「结束时间 ≤ 它的开始时间 2」的工作。在已排好的结束时间上二分,数出这样的工作有 0 份(一份都没有,它开始得太早)。这 0 份的最优组合正是 dp[0](蓝色)。
两条路算清楚:不接这份,收益沿用 dp[1] = 50;接这份,收益是它配上 dp[0] = 0,再加自己的 10,得 10。不接更高,选 50。
第 2 格结算:dp[2] = 50(绿色锁定)。后面更晚结束的工作会接着用它。
现在要填 dp[3]。当前这份工作开始 3、结束 5、收益 40。它有两条路:不接它,或者接它。先看接它能配上谁。
接它的话,前面只能配「结束时间 ≤ 它的开始时间 3」的工作。在已排好的结束时间上二分,数出这样的工作有 1 份(结束时间 3 都 ≤ 3)。这 1 份的最优组合正是 dp[1](蓝色)。
两条路算清楚:不接这份,收益沿用 dp[2] = 50;接这份,收益是它配上 dp[1] = 50,再加自己的 40,得 90。接它更高,选 90。
第 3 格结算:dp[3] = 90(绿色锁定)。后面更晚结束的工作会接着用它。
现在要填 dp[4]。当前这份工作开始 3、结束 6、收益 70。它有两条路:不接它,或者接它。先看接它能配上谁。
接它的话,前面只能配「结束时间 ≤ 它的开始时间 3」的工作。在已排好的结束时间上二分,数出这样的工作有 1 份(结束时间 3 都 ≤ 3)。这 1 份的最优组合正是 dp[1](蓝色)。
两条路算清楚:不接这份,收益沿用 dp[3] = 90;接这份,收益是它配上 dp[1] = 50,再加自己的 70,得 120。接它更高,选 120。
第 4 格结算:dp[4] = 120(绿色锁定)。后面更晚结束的工作会接着用它。
表填满,最右一格 dp[4] = 120 就是答案。
回看具体选了谁:接第 1 份(结束 3、收益 50),它结束在 3;再接第 4 份(开始正好是 3、结束 6、收益 70),开始时间等于上一份结束时间,不冲突。两份相加 50 + 70 = 120,正是最大收益。
边界先想清:结束等于下一份开始算可接;开始时间相同的工作互斥,只能留一份。
两个追问,核心是认出「带权区间调度 = 排序 + DP + 二分」这个可推广的母题。
参考代码
from typing import Listfrom bisect import bisect_rightclass Solution: def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int: jobs = sorted(zip(endTime, startTime, profit)) ends = [e for e, _, _ in jobs] dp = [0] * (len(jobs) + 1) for i, (e, s, p) in enumerate(jobs, 1): j = bisect_right(ends, s, 0, i - 1) dp[i] = max(dp[i - 1], dp[j] + p) return dp[-1]复杂度
- 时间：O(n log n)，排序 O(n log n);填表每格一次二分 O(log n),共 n 格
- 空间：O(n)，dp 数组与 ends 数组,长度都是 n 级别
易错点
面试追问把动画讲成自己的话
追问这题和经典的「活动选择 / 区间调度」有什么区别?
追问如果把二分换成对每个 i 线性往前扫找可配工作,复杂度会怎样?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
让字符串成为回文串的最少插入次数
LeetCode 1312 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题