1. 先说这道题的含金量算法设计与分析课程里习题6.3这种编号往往卡在一个很微妙的位置——前几章刚讲完分治和贪心后面紧接着就是动态规划而6.3恰好就是让你把前两种思维揉碎了再重新拼起来的转折点。我当年做这道题的时候第一感觉是“这不就是贪心吗”结果被一组简单的反例教做人了。这道题的核心背景是一个典型的带权区间调度问题通俗地说你有若干项任务每项任务有开始时间、结束时间和收益同一时间只能做一个任务问怎么选能让总收益最大。听着和活动选择问题很像但多了“收益”这个维度之后贪心策略就不好使了必须老老实实引入动态规划。这一点恰恰是这道题真正的考点不是让你背状态转移方程而是让你自己从“为什么贪心不行”开始一步步把递推关系推导出来。这篇文章适合正在学算法设计与分析课程的人、准备复试或者刷题面试的读者也可能帮到在工作中偶尔需要做任务排程的开发者。我会从题目本身出发把建模过程、递推推导、代码实现、复杂度分析、常见卡点全部过一遍末尾再分享一些我自己踩过的坑。整个过程读完你应该能独立把这个“习题6.3”变成自己的东西遇到任何变体也能解。2. 从题目抽象到问题建模这题到底在问什么2.1 原题场景还原习题6.3的原始描述一般是这样的某实验室近期申报了一批实验任务每个任务用一个三元组表示——开始时间 s_i、结束时间 f_i、预期收益 w_i。实验室同一时间只能运行一个任务要求从这批任务中选出一个子集使得子集内任意两个任务在时间上不重叠同时总收益最大。数据规模通常会给出一个上限比如 n ≤ 10^5s_i 和 f_i 的范围在某段时间轴内。看到这个规模基本上就能确定目标复杂度得是 O(n log n) 或更优O(n²) 大概率是过不了的。我第一次看到这个题第一反应是“这不是活动选择问题吗按结束时间排序然后贪心就完了”。但注意活动选择问题里每个任务的收益是相等的所以局部最优选结束时间最早的能推出全局最优换成收益不等之后一个结束时间稍晚但收益极高的任务完全可能压过好几个小任务的总和贪心选出来的很可能不是最优解。2.2 为什么贪心在这里失效我用一个简单的例子说明。三个任务任务As0, f1, w50任务Bs1, f2, w100任务Cs0, f2, w101如果按结束时间排序贪心策略会先看Af1能选再看到Bf2和A不重叠选总收益150。但如果直接选C收益是101还不如贪心的150。这个例子好像贪心赢了但换一组数据任务As0, f1, w50任务Bs1, f2, w100任务Cs0, f2, w160这时贪心依然选A和B收益150但最优解显然是选C收益160。这就是典型的“局部选择最优但全局不一定最优”。原因是贪心只考虑了时间上的紧凑性没有把收益差异纳入决策。带权区间调度问题的标准解法就是把“选”与“不选”两种情况都算一遍取最大值——这天然就是动态规划的决策方式。2.3 建模的关键点排序预处理动态规划的第一步是确定状态之间的“顺序”。对于区间调度问题最自然的顺序就是按结束时间从小到大排序。排序之后我们才能方便地找到“最后一个与当前任务相容的任务”是谁。假设排序后的任务序列为 task[1..n]我们定义 p_i 为满足 f_j ≤ s_i 的最大下标 j即结束时间不超过任务 i 开始时间的最后一个任务。这个 p_i 是后续递推的核心索引找它的过程可以用二分查找这也是整个算法复杂度能压到 O(n log n) 的关键。这里有个容易忽略的细节排序时如果结束时间相同应该怎么处理我的经验是按开始时间再排一次保证稳定性但这不影响递推的正确性只要 p_i 的查找逻辑与排序保持一致就行。3. 状态定义与递推推导把“为什么”讲透3.1 状态 dp[i] 的含义定义 dp[i] 表示从前 i 个任务排序后中能获得的最大总收益。注意这里不是“第 i 个任务必须选”的含义而是一个“考虑前 i 个任务的最优值”的全局状态。很多初学者会在这里混淆导致后面递推写错。为什么这样定义状态因为区间调度的决策天然有“顺序”的概念任务之间通过时间先后形成前驱关系。当我们枚举到第 i 个任务时所有可能与第 i 个任务冲突的任务都在它之前被处理过了。这样递推的时候只需要关注两个子问题。3.2 状态转移方程对于第 i 个任务我们有两种决策不选第 i 个任务收益直接继承前 i-1 个任务的最优值即 dp[i-1]。选第 i 个任务收益等于 w_i 加上前 p_i 个任务的最大收益即 dp[p_i] w_i。为什么要用 p_i 而不是 i-1因为如果选了任务 i任何与它时间重叠的任务都不能再选。而前 p_i 个任务下标从1到 p_i的结束时间都不超过 s_i所以它们全部与任务 i 相容。换句话说dp[p_i] 是“在考虑选第 i 个任务的前提下之前还能再选哪些任务”的最优解。于是状态转移方程写出来是dp[i] max(dp[i-1], dp[p_i] w_i)初始条件是 dp[0] 0表示一个任务都不选时收益为0。3.3 边界条件与初始化技巧二分查找 p_i 时需要在一个“结束时间数组”上找 ≤ s_i 的最大下标。我用的是 C 标准库的 upper_bound 再减一或者 Python 的 bisect_right 再减一。具体来说假设 endp[1..n] 是排序后各任务的结束时间目标就是找 endp ≤ s_i 的最大位置这正好是 bisect_right(endp, s_i, 0, i-1) 的返回值减一。这里有个数组下标从0还是从1开始的问题。我的建议是下标从1开始方便 dp[p_i] 中的 p_i 可能为0dp[0] 作为哨兵。如果用0基需要在代码里多写很多边界特判而且容易漏掉 p_i 可能为 -1 的情况。还有一个值得注意的细节任务 i 自身的结束时间如果比某个任务 j 的开始时间还早那么 j 可能是 i 的后继但我们在递推时只往前看不需要关注后继因为 dp[i] 的递推是单向地从较小下标到较大下标天然不会漏掉任何方案。4. 代码实现与核心环节拆解4.1 完整可运行的示例代码我用 Python 写一个清晰版本方便直接对照理解C版的逻辑基本一致。from bisect import bisect_right def max_profit(tasks): # tasks: list of (start, end, weight) if not tasks: return 0 # 按结束时间排序 tasks.sort(keylambda x: x[1]) n len(tasks) starts [tasks[i][0] for i in range(n)] ends [tasks[i][1] for i in range(n)] weights [tasks[i][2] for i in range(n)] # 1-based dpdp[0]0 dp [0] * (n 1) # 记录选择的路径用于回溯方案可选 prev [0] * (n 1) choice [False] * (n 1) for i in range(1, n 1): # 找 p_i最后一个结束时间 当前任务开始时间的任务 # 注意 bisect_right 在 ends 里找 starts[i-1] pos bisect_right(ends, starts[i-1]) # 返回第一个 starts[i-1] 的位置 p_i pos - 1 # 由于是1-based下标p_i 直接就是符合条件的任务数 # 注意ends 列表长度为 npos 的范围是 0..n # 选第i个任务时之前的收益是 dp[p_i]因为 p_i 是符合条件的最大下标 if dp[i-1] dp[p_i] weights[i-1]: dp[i] dp[i-1] choice[i] False else: dp[i] dp[p_i] weights[i-1] choice[i] True prev[i] p_i # 回溯方案 selected [] i n while i 0: if choice[i]: selected.append(tasks[i-1]) i prev[i] else: i - 1 selected.reverse() return dp[n], selected # 示例 tasks [(0, 1, 50), (1, 2, 100), (0, 2, 160)] print(max_profit(tasks))4.2 逐行解读这代码为什么这么写二分查找那里是新手最容易懵的地方。我用 Python 的 bisect_right 在 ends 数组里找第一个大于 starts[i-1] 的位置得到 pos那么 pos-1 就是最后一个结束时间不超过 starts[i-1] 的位置。由于数组下标从0开始但任务编号从1开始pos-1 恰好就是“符合条件的前置任务数量”。举个例子如果当前任务是第3个任务starts[2]5ends[2,4,7]bisect_right 返回2因为 ends[0]2 ≤ 5, ends[1]4 ≤ 5, ends[2]7 5pos-11说明任务1和任务2都可以作为前置任务dp[1]就是选择任务3时“前面还能取得的最大收益”。注意我找 p_i 的时候用了整个 ends 数组而不是 ends[:i-1]。这看起来好像会找到未来的任务但实际上不会——因为当前任务 i 是枚举过程中遇到的如果某个未来的任务 j 结束时间也小于等于当前任务的开始时间那说明 j 在时间上排在当前任务之前但它实际还没被枚举到dp[j] 也是未知的。不过由于排序后结束时间是递增的ends 中所有小于等于 starts[i-1] 的任务它们的下标一定都小于当前任务的下标除非结束时间相等这种情况需要额外处理。如果结束时间有相等的情况可能存在下标大于 i 但结束时间等于 starts[i-1] 的任务此时 p_i 可能被错误地计算成大于 i-1。为了避免这个隐患我建议把二分查找的范围严格限制在前 i-1 个任务里也就是对 ends[:i-1] 做查找。上面的示例代码为了简洁用了全量数组但如果结束时间有相等的情况严格写法应当限制范围。4.3 严格限定查找范围的修正版本如果把二分查找范围限定在 ends[:i-1] 中代码稍微变一下pos bisect_right(ends[:i-1], starts[i-1]) p_i pos # 因为 ends[:i-1] 长度就是 i-1pos 范围 0..i-1恰好等于符合条件的任务数量注意这里 p_i 直接等于 pos不需要减一因为切片后索引从0开始pos 的含义是“前 i-1 个任务中结束时间不超过 starts[i-1] 的数量”正好是符合条件任务的最大下标1-based。这个写法更严谨我平时更推荐这个版本。4.4 回溯输出最优方案很多教材只要求输出最大收益但实际面试或项目中我们往往还需要具体的任务选择方案。回溯的思路很直白从 dp[n] 开始如果第 i 个任务被选中了choice[i] 为 True就把它加入结果集然后跳到 prev[i] 继续回溯否则就跳到 i-1。这个过程的正确性依赖于递推时记录的选择状态代码里我已经写了完整的实现。有一点值得提醒choice[i] 为 True 的情况下prev[i] 是选第 i 个任务时的前驱下标而 choice[i] 为 False 时prev[i] 没有被赋值回溯时直接 i-1 就行。这种“只记录关键决策”的设计能省不少内存尤其 n 达到 10^5 时额外开一个 prev 数组已经是必要的了不要再开二维数组。5. 复杂度分析与优化思路不仅仅是 O(n log n)5.1 时间与空间复杂度推导时间开销主要在三部分排序 O(n log n)、二分查找每个任务一次O(log n)、主循环 O(n)。总复杂度 O(n log n)。空间上存储任务信息 O(n)、ends 和 dp 各 O(n)、回溯用的 prev 和 choice 也是 O(n)加起来 O(n)。其中 dp、prev、choice 都可以用数组实现没有递归栈开销所以实际存储很轻。如果数据规模特别大比如 n 到 10^6排序仍然是瓶颈但 O(n log n) 在绝大多数场景下都够用了。可以把 ends、starts 提前建好减少重复的内存访问二分查找用 C 的 lower_bound 或 Python 的 bisect 模块它们的常数都很小不会成为性能瓶颈。5.2 进一步优化的可能性如果任务的起始和结束时间都在一个很小的整数范围内比如时间轴是 0 到 10000可以考虑用树状数组或线段树优化前缀最大值查询把复杂度降到 O(n log T)T 为时间范围甚至在离散化后变成 O(n log n)。不过对于习题6.3这个位置来说二分查找的 O(n log n) 已经是最佳写法了。再往深走一步如果时间范围极小而 n 极大可以考虑基于时间的滚动数组。另一个优化点是内存。如果不需要回溯方案直接把 prev 和 choice 数组去掉只保留 dp。很多在线评测平台只要求输出最大收益这样能把空间降到 O(n) 最小值。我自己的习惯是保留回溯因为“能输出方案”是一个加分项面试时主动展示这个能力往往能加印象分。5.3 与无权区间调度的对比习题6.3和教材前几章的活动选择问题有血缘关系但结论差别很大。无权版本用贪心就能得到最优解带权版本必须用动态规划。很多人会困惑什么时候能用贪心什么时候必须上 DP我的判断标准是如果决策只取决于“是否可行”而不包含“不同价值”贪心有大概率可行一旦每个解法的“收益”各不相同且不可比较就一定要用 DP。这里的“不可比较”指的是收益大小和任务时长、时间位置没有单调关系无法通过局部贪心推出全局最优。这个判断标准可以泛化到很多问题比如背包问题0-1背包必须用DP分数背包可以贪心、最长递增子序列O(n log n)动规二分等。习题6.3就是帮你建立这种直觉的训练场。6. 常见问题与排查技巧实录6.1 卡了我最久的二分查找边界错误这个错误非常经典。我第一次写的时候用 lower_bound 而不是 upper_bound导致找出来的 p_i 是“第一个结束时间 ≥ 开始时间”的位置而不是“最后一个结束时间 ≤ 开始时间”递推结果就反了。如果要求“相容”必须是 结束时间 ≤ 开始时间所以要用 upper_bound / bisect_right再向左移动一位。如果用 lower_bound会把正好在开始时间点结束的任务排除掉浪费了很多可行方案。还有一种情况是调用 bisect_right 时作用在 ends 全量数组上而没注意到下标偏移。当排序后存在相同结束时间时可能把 p_i 算成大于 i-1从而读到 dp 的“未来值”结果自然是错的。遇到这种问题调试技巧是打印每个 i 的 p_i 和 dp[i]对照手动推导的小数据集很快就能定位。6.2 排序稳定性与相等结束时间的处理如果两个任务结束时间相同排序后它们的先后顺序会影响二分查找的结果但理论上不应该影响最优解。不过为了代码的确定性我建议按结束时间升序排结束时间相同时按开始时间升序排。这样任何合法输入都能得到可复现的结果。另外一个隐蔽问题是如果任务的开始时间或结束时间可能出现负数或者时间轴偏移很大直接用原始数值排序和二分没问题但要注意索引范围。二分查找的时间复杂度只依赖 log n和时间值域无关所以负数时间也不用特殊处理。6.3 典型错误的报错样例与修正一个容易写错的版本是把转移方程写成 dp[i] max(dp[i-1], dp[i-1] w_i)。这个式子看起来合理但实际上没有排除重叠任务。例如任务C的开始时间早于任务A的结束时间时你选了C又选了A冲突了都不知道。正确写法必须用 p_i 而不是 i-1。另一个常踩的坑是把 dp 数组初始化成负无穷然后枚举时又没考虑 dp[p_i] 可能查不到值。由于我们已经让 dp[0]0 作为哨兵p_i 最少是0所以不会出现负无穷的情况。如果题目改成“必须恰好选择若干任务”之类的变体才需要特殊处理。如果出现答案小于0的情况某些题目允许负收益就要重新审视初始值设定。通常带权区间调度默认收益非负如果有负收益可以选择不做任何任务答案至少为0dp[0] 和 max 操作都能保证这一点。6.4 提升鲁棒性的小技巧我建议写完代码后立刻用三组测试数据验证全部任务互不重叠最优是所有任务总和、全部任务两两重叠最优是收益最大的那个、混合情况需要仔细看递推是否选对。这组测试能覆盖大部分边界条件。我最初在第二组数据上就翻过车因为把转移方程错误地写成了 dp[i] max(dp[i-1], dp[i] w_i)。另外如果某个任务的收益远大于其他任务之和算法也应该正确选择它。做压力测试时可以随机生成 n1000 的数据用 O(n²) 的暴力和 O(n log n) 的优化代码对拍所有结果一致基本就能证明实现无误。对拍是我强烈推荐的验证方式比人肉模拟可靠得多。7. 变体问题与扩展思考7.1 如果任务可以重复选择习题6.3的原始场景是每个任务只能选一次。但如果把题目改成“同类任务可以重复选择”就变成了完全背包式的区间调度问题解法会有所不同需要在时间轴上做 DP。这个变体在真实世界的项目排期中很常见比如重复性的流水线任务排布值得想一想思路变化。7.2 如果要求最小化总时间而不是最大化收益有些调度场景下收益换成了代价目标是选择一组相容任务使总运行时间最小。此时可以把“收益”替换成“时间长度”但状态定义不变递推变成 dp[i] min(dp[i-1], dp[p_i] duration_i)。注意初始化要改成一个大数而非0。这种“换个目标函数但骨架不变”的题目考试里特别喜欢考掌握了原题就等于掌握了一整类题。7.3 如果任务之间存在依赖关系当任务之间不仅有时间约束还必须在某个前置任务完成后才能开始这就变成了 DAG 上的最长路径问题本质还是动态规划但状态的定义需要增加维度。习题6.3其实已经暗含了“时间顺序就是依赖顺序”的思想扩展之后就是项目管理中的关键路径法。一通百通值得自己去推一遍。8. 写在最后的经验心得我带过不少学弟学妹写这道题发现大家的问题往往不是看不懂递推式而是卡在“为什么这里要排序”和“为什么二分查找可以找到 p_i”这两个环节。经过反复讲解我认为最好的理解方式是把排序后的任务想象成一条时间轴上的线段dp[i] 就是“已经看完了前 i 个线段我能拿到的最优收益”。每个新线段出现时要么跳过它要么把它拼到一条最近的不冲突的“历史最优序列”后面。二分查找做的是快速找到“最近的不冲突的位置”而不是一个个往前扫描。代码写完只是第一步。如果真的想把这一类问题内化我建议做三件事第一手写一个 7~8 条数据的小样例把所有 dp 值逐个手动算一遍第二用对拍程序生成随机数据验证代码第三尝试把代码改成输出选择方案并且用回溯法验证方案里确实没有时间冲突。做到这三点习题6.3就再也不只是“背下来的一道题”了。说实话这道题在整本教材里不算最难但它承上启下把贪心、排序、二分、动态规划、回溯输出全部串了一遍。吃透这道题之后再遇到带权区间调度、任务排程、资源分配这一类现实问题你脑子里会直接浮现出这个 dp 框架而不是从头再去推一遍。这就是算法题该有的价值——不是刷完就忘而是变成一种可以随时调用的思维工具。