题干与适用场景
给定任务 (start, end, reward)，选择一组两两兼容的任务最大化收益。若一个任务在时间 t 结束，另一个在 t 开始，两者可以同时选择。示例：(1,3,50)、(3,5,40)、(2,6,100) 的最优选择是前两个任务，总收益 90。题目属于 coding，核心能力是区间排序、前驱查询和动态规划，不因实现语言归入前端。
公开算法题资料把 weighted interval/job scheduling 用作动态规划与区间模式练习；公开面经记录也出现过 interval scheduling 变体。应描述可核验的算法要求，不声称无法核验的面试频率。
面试官考察点
- 能否先按结束时间排序，把“最后选择的任务”变成有序决策。
- 能否定义
p(i)：在任务i开始前结束的最后一个兼容任务。 - 能否写出“跳过当前任务”与“选择当前任务”的完整递推，而非贪心地只选当前收益最高者。
- 能否用二分查找把前驱查询降到
O(log n)，并说明是否需要恢复所选任务。 - 能否处理
end == start、相同结束时间、空数组和收益为零等边界。
回答前需要澄清的问题
- 结束时间等于开始时间是否兼容？本文按兼容处理，即前驱条件为
end <= start。 - 收益是否允许负数？若允许，应明确可以一个任务都不选，基线收益为
0。 - 是否只返回最大收益？本文同时恢复任务集合，若只要收益可省略回溯数组。
- 时间是否为整数？排序只需要可比较值；二分查找不要求连续整数。
- 是否允许同一任务重复？默认每个输入任务最多选一次。
- 输入是否可能包含
start > end？标准约束应拒绝或预先规范化，不能让递推隐式吞掉坏数据。 - 相同区间如何处理？按输入索引保留稳定的 tie-break，结果收益相同即可。
30 秒回答框架
“我先按 end 升序排序，设 dp[i] 表示前 i 个任务能取得的最大收益。对第 i 个任务，用二分查找找到最后一个满足 end <= start[i] 的任务数量 p。状态转移是 dp[i] = max(dp[i-1], reward[i] + dp[p])：前者跳过当前任务，后者选择当前任务并接上兼容前缀。保存选择标记后从末尾回溯任务。排序是 O(n log n)，每次二分也是 O(log n)，总时间 O(n log n)，空间 O(n)。”
分步骤深入解答
第一步：说明贪心为何不够。
按最早结束时间的经典贪心只适合每个任务收益相同。这里收益不同，短任务可能收益很低，不能仅凭结束时间或单个收益做局部决定。
第二步：定义有序状态。
排序后令 dp[i] 表示前 i 个任务（下标 0..i-1）的最优收益，dp[0] = 0。这样不选择任务 i-1 时直接落到 dp[i-1]。
第三步：计算前驱。
对任务 i-1，找最大的 j < i-1，满足 end[j] <= start[i-1]。用结束时间数组二分查找，返回“可兼容任务数量” p，选择该任务的收益就是 reward[i-1] + dp[p]。
第四步：写出递推与恢复。
dp[0] = 0
for i = 1..n:
skip = dp[i - 1]
take = reward[i - 1] + dp[p(i - 1)]
dp[i] = max(skip, take)
chose[i] = take > skip从 i = n 倒推：若 chose[i] 为真，记录任务 i-1 并跳到 p(i-1)；否则跳到 i-1。相等时固定选择跳过或选择一种 tie-break，收益都正确。
第五步：给出正确性证明。
考虑前 i 个任务的任意最优解。它要么不含任务 i-1，收益至多为 dp[i-1]；要么含任务 i-1，其余任务必须来自前 p(i-1) 个任务，收益至多为 reward[i-1] + dp[p(i-1)]。两种情况的最大值正是递推式。归纳基底 dp[0]=0，因此所有 dp[i] 都最优。
第六步：实现时守住边界。
二分查找必须用 <=，否则会错误排除刚好首尾相接的任务。收益为零时允许选择空集；若收益可能为负数，dp 仍从零开始。回溯结果需反转，因为恢复顺序是从后往前。
第七步：分析复杂度。
排序 O(n log n)；每个任务一次二分 O(log n)，所以总时间 O(n log n)。dp、前驱数组和回溯标记占 O(n) 空间；输出任务列表不计入辅助空间时仍需说明其大小。
第八步：何时选择替代方案。
若结束时间是小范围整数，可用坐标压缩或按时间扫描；若每个任务收益相同，可退化为最早结束时间贪心。若还有限制“最多选 k 个任务”或任务有资源维度，状态需要增加维度，不能直接套用一维递推。
高质量示范回答
“我会先按结束时间排序，并令 dp[i] 表示前 i 个任务的最大收益。对每个任务 i，二分查找最后一个 end <= start[i] 的前驱 p(i)。不选它时收益是 dp[i-1]；选它时收益是 reward[i] + dp[p(i)]，因此 dp[i] = max(dp[i-1], reward[i] + dp[p(i)])。回溯时根据两项大小恢复任务集合。证明上，任一最优解都按是否包含当前任务分成这两类，且包含当前任务时剩余任务只能来自兼容前缀。排序和二分让总时间为 O(n log n)，数组空间为 O(n)。我会重点测试首尾相接、相同结束时间、全负收益、全重叠和空输入。”
常见错误
- 按收益最高的任务贪心 → 高收益任务可能挡住两个更高总和的任务 → 用“选择/跳过”递推。
- 把结束时间相等判为冲突 → 丢掉合法相邻任务 → 前驱条件使用
end <= start。 - 只按开始时间排序 →
dp[i-1]不再代表稳定的已处理前缀 → 按结束时间排序。 - 前驱查找线性扫描 → 总复杂度退化到
O(n²)→ 使用结束时间数组二分。 dp从第一个收益初始化 → 全部负收益时无法选择空集 → 默认dp[0] = 0。- 回溯后忘记反转 → 输出任务顺序倒置 → 从后往前收集后反转。
- 相等收益时使用未定义行为 → 测试结果不稳定 → 固定 tie-break，并只保证收益与兼容性正确。
- 错误声称可以扩展到带资源限制 → 一维状态无法表达额外约束 → 明确增加维度或重新建模。
追问及应对
追问一：为什么不能只选收益最高的任务？
因为收益最高的单个任务可能覆盖两个互不重叠、总收益更高的任务。区间兼容性使选择具有全局影响，递推同时比较选择与跳过才能保留最优解。
追问二：如何只用 O(n) 时间？
若时间坐标是小范围整数，可以按结束时间做线性扫描，并用直接寻址找前驱；一般比较模型下排序本身需要 O(n log n)，本文复杂度不能无条件降到线性。
追问三：如何恢复具体任务？
保存 chose[i] 或比较时记录父指针。从 i=n 开始，选择当前任务就加入结果并跳到 p(i)，否则减一；最后反转结果。
追问四：如果最多只能选 k 个任务？
增加选取数量维度，例如 dp[i][c] 表示前 i 个任务选 c 个的最大收益，转移仍比较跳过与选择，但空间和时间都会增加。
追问五：如果任务收益会随相邻任务变化？
简单的独立收益假设失效。需要把相邻关系纳入状态，或把收益变化抽象为边/转移成本；不能继续使用原递推式而不证明。
追问六：全是相同结束时间时怎么办？
保持稳定排序即可。每个任务的前驱通常相同，递推仍会逐个比较；若区间完全相同，只会保留收益更优的选择，兼容性不受影响。
追问七：什么时候贪心是正确的？
当所有任务收益相同、目标是最多选择任务时，按最早结束时间的贪心有交换论证。收益不同后该论证不再成立，应切换到加权动态规划。