一组预约各占一个时间区间并带有收益。选出互不冲突的预约，使总收益最大。最早结束的预约为后续留下较多时间，但它可能收益很小；直接套用无权区间调度的贪心规则会丢掉更好的带权方案。

例如[0,1)和[1,2)的收益各为2，[0,2)的收益为5。最早结束的贪心可以选前两个，收益4；只选长区间却有5。动态规划需要保存的是尚未选择最后一个区间时，各个前缀能达到的最好收益。

输入、兼容与恢复结果

输入n个三元组(start,end,weight)，端点和收益为整数，要求start<end。区间采用半开语义，相接端点兼容：一个区间的end等于下一个的start时可以同时选择。收益可以为负或0，空方案始终合法。

每个输入位置是独立ID，相同区间也保留不同ID；它们有正长度且彼此重叠，不能同时选择。输出包括最优收益和一组实际选择的ID，ID按算法的结束时间顺序返回。目标并未要求所有最优解，也不要求ID字典序最小。

教学接口对start≥end抛出ValueError。特别是零长度区间没有直接混入常规区间证明：空区间怎样参与收益和兼容，需要另外约定，不能靠排序偶然得到结果。

为什么按结束时间建立前缀

把区间按(end,start,id)排序，重新编号1到n。定义p(j)为j之前最后一个满足end≤start_j的区间编号；不存在时为0。由于end已排序，所有可放在j之前的区间恰好构成前缀1到p(j)。

若一个更早结束的区间i不与j重叠，它必须在j开始之前结束。它不可能整体位于j之后，因为start_i<end_i≤end_j，而start_i≥end_j会矛盾。正长度条件在这里排除了边界歧义。

p(j)可在此前的结束时间数组中用上界二分得到。查找的是end≤start_j，因此使用bisect_right；换成下界二分会漏掉恰好相接的区间。搜索范围只取j之前，明确保持p(j)<j。

状态必须覆盖互斥且完备的选择

令D[j]为前j个区间能取得的最大总收益，D[0]=0。一个最优方案对区间j只有两种情况：不选择j，则它属于前j−1个区间；选择j，则其他区间只能来自前p(j)个区间。

D[j]=max⁡{D[j−1], wj+D[p(j)]}.D[j]=\max\{D[j-1],\ w_j+D[p(j)]\}.

上界方向：任何合法方案落入其中一种情况，收益不超过相应候选。可达方向：前j−1个的最优方案仍然合法；前p(j)个的最优方案与j合并也合法，因此两项候选都能实现。按j归纳，递推值恰等于最优值，而不只是一个松上界。

只保存“最后一个选中区间的收益”不够。后续需要比较的是完整前缀的最佳总收益，且所需前缀p(j)可能离j很远。状态设计要回答未来转移需要什么信息，而不是把循环下标直接换成数组下标。

负收益不需要特殊转移：D[0]=0且每步可以不选，最优收益永不低于0。若问题改成“必须至少选一个”，初值和状态含义都要改变，不能沿用空方案合法的答案。

从表格恢复真正的方案

如果w_j+D[p(j)]严格大于D[j−1]，记录选择j并跳到p(j)；否则不选，跳到j−1。相等时固定选择不选分支，只是让输出可复跑，不声称它满足题目没有要求的二级最优标准。

每次跳转编号严格减小，所以恢复至多经过n步。选择分支的下一状态限定到兼容前缀，所输出区间互不重叠；各条选择边的收益相加等于D[n]。恢复过程中先得到逆序ID，最后反转为结束时间顺序。

对区间(0,3,5)、(1,2,4)、(2,4,4)，排序后依次是原ID1、0、2。p依次为0、0、1，D依次为0、4、5、8。恢复先选原ID2，再跳到第1个区间并选原ID1，最终返回收益8与ID列表[1,2]。这些数是手算推导，不是运行计时。

同一递推也是DAG上的最长路

建立节点0到n。对每个j，从j−1到j连一条权重0的边，表示跳过；从p(j)到j连权重w_j的边，表示选择。所有边都从较小编号指向较大编号，因此天然无环，0到n的最长路径就是D[n]。

路径中选择边对应兼容区间；反过来，一组按结束顺序排列的合法区间也能由选择边与必要的跳过边形成路径。这个对应解释了为什么按编号递增计算可以一次完成，不需要对状态反复更新。

把递推看作DAG不表示任意递归都能直接改成这种表格。若状态依赖形成环，就没有当前的拓扑顺序；若两个看似相同的状态仍因历史不同而有不同后续选择，它们也不能安全合并。

时间、空间与状态压缩的边界

排序O(n log(n+1))，n次二分共O(n log(n+1))，表格和恢复各O(n)。总时间最坏O(n log(n+1))，额外空间O(n+1)，按端点、收益加法及比较为单位成本计算；大整数位长成本另计。

这些是确定性最坏界，既不依赖随机输入，也没有高概率假设。记忆化若重复扫描寻找p(j)，可能把预处理做成O(n²)；同一个转移公式并不自动带来同一个运行成本。

不能仅因D[j]写在一行递推里就压缩成两个变量。它依赖的D[p(j)]可指向任意早先前缀，删除旧值会丢失未来需要的信息。22篇保留完整表与恢复记录，23篇再讨论在明确依赖结构下减少空间或搜索范围。

可复跑检查

实现位于examples/advanced-algorithms/weighted_intervals.py，调用weighted_schedule(intervals)得到(收益, ID列表)。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_weighted_intervals.py

独立参照枚举全部子集，逐对检查区间是否相容，再计算最大收益。检查同时验证恢复ID不重复、均来自输入、区间兼容、收益等于DP输出，不强求恢复方案等于某个任意挑选的最优子集。

本次执行通过1555个短实例，对照22621个子集；7个边界实例覆盖相接、负坐标、同结束时间、重复区间和全负收益。固定种子20260920的200个随机实例另对照34699个子集，还检查2个确定性平局结果与3个非法区间拒绝。真实stdout保存在examples/advanced-algorithms/results/weighted_intervals.json。

有限穷举用于发现p的边界与恢复跳转错误，不替代状态完备性证明；也没有测量业务调度延迟。若加入机器数、间隔时间、必须选几个预约等约束，需要重新检查状态是否仍足够，不能只改收益函数。

练习

  1. 在手算例中把最后一个区间的start从2改成1，重新计算p和D，并恢复一组方案。解释为什么只改兼容判断而不重算p会使用过期状态。
  2. 把任务改成“恰好选择两个区间”。给出包含选择数量的状态与不可行初值，说明一维D[j]为什么不足以区分零个、一个和两个区间的方案。

参考资料