带权区间调度问题（Weighted Interval Scheduling） 题目描述 给定一组区间，每个区间包含开始时间 start_i 、结束时间 end_i 和权重 weight_i 。要求选择若干互不重叠的区间，使得这些区间的权重之和最大。注意：区间互不重叠指任意两个被选区间在时间上不重叠（结束时间等于另一个的开始时间视为不重叠）。 示例 输入： intervals = [(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4)] 输出：最大权重和 = 10（选择区间1和区间4，权重5+4=9；或选择区间2和区间4，权重6+4=10，后者更优） 解题过程 步骤1：问题分析 目标：最大化权重和，且区间不重叠。 关键点：若直接枚举所有子集，复杂度为O(2^n)，不可行。需用动态规划优化。 步骤2：预处理 将所有区间按结束时间 end_i 升序排序。排序后示例为： [(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4)] （假设输入已按结束时间排序） 定义 p(j) ：对于区间 j ， p(j) 是最大的索引 i （i < j），使得区间 i 与区间 j 不重叠。若不存在， p(j) = -1 。 计算 p(j) ：对每个区间 j ，从 j-1 向前找到第一个满足 end_i ≤ start_j 的区间 i 。 步骤3：动态规划状态定义 定义 dp[i] ：考虑前 i 个区间（按结束时间排序）时，能获得的最大权重和。 步骤4：状态转移方程 对于第 i 个区间（索引从1开始），有两种选择： 不选区间 i ：则 dp[i] = dp[i-1] 。 选区间 i ：则需排除所有与区间 i 重叠的区间，最大权重为 weight_i + dp[p(i)] （其中 p(i) 是最后一个不重叠的区间索引）。 转移方程： dp[i] = max(dp[i-1], weight_i + dp[p(i)]) 注意：若 p(i) = -1 ，则 dp[p(i)] 视为0。 步骤5：计算过程（以示例为例） 区间排序后： 0: (1,3,5) 1: (2,5,6) 2: (4,6,5) 3: (6,7,4) 计算 p(j) ： j=0：无前驱，p(0)=-1 j=1：找 end_ i ≤ start_ 1=2 → 区间0的end=3>2，无匹配，p(1)=-1 j=2：找 end_ i ≤ start_ 2=4 → 区间0的end=3 <4，匹配；区间1的end=5>4，停止。p(2)=0 j=3：找 end_ i ≤ start_ 3=6 → 区间2的end=6≤6，匹配。p(3)=2 计算 dp ： i=0：dp[ 0] = max(0, 5+dp[ -1 ]) = max(0,5+0)=5 i=1：dp[ 1] = max(dp[ 0]=5, 6+dp[ -1 ]=6) = 6 i=2：dp[ 2] = max(dp[ 1]=6, 5+dp[ 0 ]=5+5=10) = 10 i=3：dp[ 3] = max(dp[ 2]=10, 4+dp[ 2 ]=4+10=14) = 14 最大权重和 = dp[ 3 ] = 14（选择区间0、2、3，权重5+5+4=14） 步骤6：复杂度分析 排序：O(n log n) 计算 p(j)：对每个 j 二分查找，O(n log n) DP 计算：O(n) 总复杂度：O(n log n) 步骤7：扩展思考 若需输出具体区间方案，可通过 dp 数组反向追踪选择路径。 若权重均为1，则退化为经典的无权区间调度问题（贪心选择结束最早的区间）。