企业官网建设流程全解析

1. 先说这道题的含金量

算法设计与分析课程里，习题6.3这种编号，往往卡在一个很微妙的位置——前几章刚讲完分治和贪心，后面紧接着就是动态规划，而6.3恰好就是让你把前两种思维揉碎了再重新拼起来的转折点。我当年做这道题的时候，第一感觉是“这不就是贪心吗”，结果被一组简单的反例教做人了。

这道题的核心背景是一个典型的带权区间调度问题，通俗地说：你有若干项任务，每项任务有开始时间、结束时间和收益，同一时间只能做一个任务，问怎么选能让总收益最大。听着和活动选择问题很像，但多了“收益”这个维度之后，贪心策略就不好使了，必须老老实实引入动态规划。这一点恰恰是这道题真正的考点：不是让你背状态转移方程，而是让你自己从“为什么贪心不行”开始，一步步把递推关系推导出来。

这篇文章适合正在学算法设计与分析课程的人、准备复试或者刷题面试的读者，也可能帮到在工作中偶尔需要做任务排程的开发者。我会从题目本身出发，把建模过程、递推推导、代码实现、复杂度分析、常见卡点全部过一遍，末尾再分享一些我自己踩过的坑。整个过程读完，你应该能独立把这个“习题6.3”变成自己的东西，遇到任何变体也能解。

2. 从题目抽象到问题建模：这题到底在问什么

2.1 原题场景还原

习题6.3的原始描述一般是这样的：某实验室近期申报了一批实验任务，每个任务用一个三元组表示——开始时间 s_i、结束时间 f_i、预期收益 w_i。实验室同一时间只能运行一个任务，要求从这批任务中选出一个子集，使得子集内任意两个任务在时间上不重叠，同时总收益最大。

数据规模通常会给出一个上限，比如 n ≤ 10^5，s_i 和 f_i 的范围在某段时间轴内。看到这个规模，基本上就能确定目标复杂度得是 O(n log n) 或更优，O(n²) 大概率是过不了的。

我第一次看到这个题，第一反应是“这不是活动选择问题吗，按结束时间排序然后贪心就完了”。但注意，活动选择问题里每个任务的收益是相等的，所以局部最优（选结束时间最早的）能推出全局最优；换成收益不等之后，一个结束时间稍晚但收益极高的任务，完全可能压过好几个小任务的总和，贪心选出来的很可能不是最优解。

2.2 为什么贪心在这里失效

我用一个简单的例子说明。三个任务：

• 任务A：s=0, f=1, w=50
• 任务B：s=1, f=2, w=100
• 任务C：s=0, f=2, w=101

如果按结束时间排序，贪心策略会先看A（f=1），能选；再看到B（f=2），和A不重叠，选；总收益150。但如果直接选C，收益是101，还不如贪心的150。这个例子好像贪心赢了，但换一组数据：

• 任务A：s=0, f=1, w=50
• 任务B：s=1, f=2, w=100
• 任务C：s=0, f=2, w=160

这时贪心依然选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 可能为0，dp[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(key=lambda 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 dp，dp[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 列表长度为 n，pos 的范围是 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]=5，ends=[2,4,7]，bisect_right 返回2（因为 ends[0]=2 ≤ 5, ends[1]=4 ≤ 5, ends[2]=7 > 5），pos-1=1，说明任务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-1，pos 范围 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的情况（某些题目允许负收益），就要重新审视初始值设定。通常带权区间调度默认收益非负，如果有负收益，可以选择不做任何任务，答案至少为0，dp[0] 和 max 操作都能保证这一点。

6.4 提升鲁棒性的小技巧

我建议写完代码后，立刻用三组测试数据验证：全部任务互不重叠（最优是所有任务总和）、全部任务两两重叠（最优是收益最大的那个）、混合情况（需要仔细看递推是否选对）。这组测试能覆盖大部分边界条件。我最初在第二组数据上就翻过车，因为把转移方程错误地写成了 dp[i] = max(dp[i-1], dp[i] + w_i)。

另外，如果某个任务的收益远大于其他任务之和，算法也应该正确选择它。做压力测试时，可以随机生成 n=1000 的数据，用 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 框架，而不是从头再去推一遍。这就是算法题该有的价值——不是刷完就忘，而是变成一种可以随时调用的思维工具。