题目重点：选择任意工作子集，区间不重叠，利润和最大。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- job=(start,end,profit)，半开且start<end；负利润可跳过，允许空方案。
- 工作不可拆分，结束恰等下一起点可接；只求利润，不返回计划。
解题路线
- 按end排序，dp[i]表示前i项最优。当前任务take需加上所有end≤start的前驱前缀答案，skip为dp[i]。
- bisect_right在此前的end数组找符合条件的项数，dp前缀下标恰对应该count。只在0..i里找防止考虑当前/未来任务。
- 每个最优方案要么不选当前，要么选它并搭配兼容前缀最优，因此递推完整。不能按profit最高先选，因为长任务可能挡住多个高合计利润短任务。
手动走一遍
(0,3,5),(1,2,4),(2,3,4)：选后两项利润8胜过第一项5。(0,1,−2)可空方案0；若要求至少一项，需要独立状态。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import bisect_right
def best_schedule(jobs):
jobs = sorted(jobs, key=lambda x:x[1])
if any(s >= e for s,e,p in jobs):
raise ValueError("positive-duration half-open jobs required")
ends = [e for s,e,p in jobs]
dp = [0]
for i,(start,end,reward) in enumerate(jobs):
count = bisect_right(ends, start, 0, i)
dp.append(max(dp[-1],dp[count]+reward))
return dp[-1]
复杂度
O(nlogn)时间、O(n)空间，排序及每个前驱二分；重建计划需choice/predecessor数组。
易错点与追问
容易失分的边界
- 把bisect_left用于等终点会禁止本可接的端点任务。
- 求最大可选数量的按结束时间贪心不适合加权利润。
继续深挖
- K台server并行任务怎样转成流或更高维DP？
- 如果start/end流式到达但允许取消，为什么离线排序前提消失？
