区间调度之权值最大化问题（Weighted Interval Scheduling） 题目描述 给定一组区间，每个区间有一个起始时间 \( s_ i \)、结束时间 \( f_ i \) 和一个权值 \( w_ i \)（代表该区间的重要性或收益）。要求选择一组互不重叠的区间，使得这些区间的权值之和最大。区间不能重叠（即下一个区间的起始时间必须大于等于上一个区间的结束时间）。 关键点分析 与经典区间调度问题（最大化区间数量）不同，此问题需考虑权值，可能需牺牲数量以选择高权值区间。 需动态规划（DP）高效求解，避免暴力枚举所有子集（复杂度 \(O(2^n)\)）。 解题步骤 步骤1：预处理区间 将所有区间按结束时间 \( f_ i \) 升序排序。排序后，区间索引 \( j \) 的结束时间不早于索引 \( i \)（若 \( j > i \)）。 排序目的：便于快速找到与当前区间不重叠的前驱区间。 步骤2：定义动态规划状态 设 \( dp[ i ] \) 表示考虑前 \( i \) 个区间（按结束时间排序后）时，能获得的最大权值和。 对于第 \( i \) 个区间，有两种选择： 不选第 \( i \) 个区间 ：则 \( dp[ i] = dp[ i-1 ] \)。 选第 \( i \) 个区间 ：则需找到最后一个不与第 \( i \) 个区间重叠的区间 \( p(i) \)。最大权值和为 \( w_ i + dp[ p(i) ] \)。 状态转移方程： \[ dp[ i] = \max(dp[ i-1],\ w_ i + dp[ p(i) ]) \] 步骤3：计算 \( p(i) \)（前驱区间索引） \( p(i) \) 是满足 \( f_ j \leq s_ i \) 的最大索引 \( j \)（即结束时间最晚且不重叠的区间）。 由于区间已按结束时间排序，可用二分查找快速计算 \( p(i) \)，将时间复杂度优化至 \( O(n \log n) \)。 步骤4：递推计算 \( dp[ i] \) 初始化 \( dp[ 0 ] = 0 \)（无区间时权值为0）。 按 \( i = 1 \) 到 \( n \) 顺序计算 \( dp[ i] \)，最终 \( dp[ n ] \) 即为最大权值和。 步骤5：重构最优解 从 \( i = n \) 开始反向追踪： 若 \( dp[ i] > dp[ i-1 ] \)，说明第 \( i \) 个区间被选中，将其加入解集，并跳至 \( p(i) \)。 否则跳过第 \( i \) 个区间，检查 \( i-1 \)。 示例演示 假设区间数据如下（已按结束时间排序）： | 区间 | 起始时间 | 结束时间 | 权值 | |------|----------|----------|------| | 1 | 1 | 3 | 5 | | 2 | 2 | 5 | 6 | | 3 | 4 | 6 | 4 | | 4 | 7 | 9 | 8 | 计算 \( p(i) \) ： \( p(1) = 0 \)（无前驱） \( p(2) = 0 \)（区间2与区间1重叠） \( p(3) = 1 \)（区间3与区间1不重叠，与区间2重叠） \( p(4) = 2 \)（区间4与区间3重叠，与区间2不重叠） 递推 \( dp[ i] \) ： \( dp[ 0 ] = 0 \) \( dp[ 1] = \max(dp[ 0], 5 + dp[ 0 ]) = \max(0, 5) = 5 \) \( dp[ 2] = \max(dp[ 1], 6 + dp[ 0 ]) = \max(5, 6) = 6 \) \( dp[ 3] = \max(dp[ 2], 4 + dp[ 1 ]) = \max(6, 4+5) = 9 \) \( dp[ 4] = \max(dp[ 3], 8 + dp[ 2 ]) = \max(9, 8+6) = 14 \) 最大权值和 ：\( dp[ 4 ] = 14 \)（选择区间1、3、4）。 复杂度分析 排序：\( O(n \log n) \) 计算 \( p(i) \)：\( n \) 次二分查找，每次 \( O(\log n) \) DP 递推：\( O(n) \) 总复杂度：\( O(n \log n) \)，适用于大规模数据。