带权区间调度问题 问题描述 给定一组区间，每个区间有一个开始时间、结束时间和权重（价值）。目标是选择一组互不重叠的区间，使得这些区间的总权重最大。 形式化描述： 输入：n个区间，第i个区间表示为(s_ i, e_ i, w_ i)，其中s_ i是开始时间，e_ i是结束时间，w_ i是权重 输出：一个互不重叠的区间子集，使得子集中所有区间的权重之和最大 约束：区间按结束时间排序，即e₁ ≤ e₂ ≤ ... ≤ e_ n 解题过程 步骤1：问题分析 这是一个典型的区间调度问题，与普通区间调度不同之处在于每个区间有权重值，我们需要最大化权重和而非区间数量。关键点在于如何选择区间使得它们不重叠且总价值最大。 步骤2：定义状态 定义dp[ i ]为考虑前i个区间时，能够获得的最大权重和。这里假设区间已经按照结束时间从小到大排序。 步骤3：状态转移分析 对于每个区间i，我们有两种选择： 不选择区间i：那么dp[ i] = dp[ i-1 ] 选择区间i：那么我们需要找到前一个不与区间i重叠的区间j 区间j是满足e_ j ≤ s_ i的最大索引j 此时dp[ i] = w_ i + dp[ j ] 因此状态转移方程为： dp[ i] = max(dp[ i-1], w_ i + dp[ p(i) ]) 其中p(i)表示前一个不与区间i重叠的区间的索引。 步骤4：寻找前一个不重叠区间 我们需要高效地找到每个区间i对应的p(i)。由于区间已按结束时间排序，可以使用二分查找： 对于区间i，我们需要找到最大的j，使得e_ j ≤ s_ i 这可以通过二分查找在O(log n)时间内完成 步骤5：算法实现细节 首先对区间按结束时间排序 预处理p数组：对于每个区间i，找到p(i) 初始化dp[ 0 ] = 0（考虑0个区间） 按顺序计算dp[ 1]到dp[ n ] 步骤6：具体例子 考虑区间：[ (1,3,5), (2,5,6), (4,6,5), (6,7,4) ] 排序后（已按结束时间排好）： 区间1: (1,3,5) 区间2: (2,5,6) 区间3: (4,6,5) 区间4: (6,7,4) 计算p(i)： p(1)：没有区间结束时间≤1，p(1)=0 p(2)：结束时间≤2的区间是区间1，p(2)=1 p(3)：结束时间≤4的区间是区间1，p(3)=1 p(4)：结束时间≤6的区间是区间3，p(4)=3 计算dp： dp[ 0 ] = 0 dp[ 1] = max(dp[ 0], 5+dp[ p(1) ]) = max(0, 5+0) = 5 dp[ 2] = max(dp[ 1], 6+dp[ p(2) ]) = max(5, 6+5) = 11 dp[ 3] = max(dp[ 2], 5+dp[ p(3) ]) = max(11, 5+5) = 11 dp[ 4] = max(dp[ 3], 4+dp[ p(4) ]) = max(11, 4+5) = 11 最大权重和为11，对应选择区间1和区间2。 步骤7：算法复杂度 排序：O(n log n) 预处理p数组：O(n log n)（使用二分查找） 动态规划计算：O(n) 总复杂度：O(n log n) 步骤8：重构最优解 通过记录选择情况，可以回溯找到具体选择了哪些区间。在计算dp[ i ]时，记录是选择了还是不选择当前区间，然后从后往前回溯即可得到最优解。 这个算法高效地解决了带权区间调度问题，通过动态规划和二分查找的结合，在合理的时间复杂度内找到了最优解。