带权区间调度问题 题目描述 给定n个区间，每个区间有一个开始时间s_ i、结束时间e_ i和权重w_ i。你需要选择一组互不重叠的区间，使得这组区间的总权重最大。 形式化地说：给定区间集合I = {[ s_ 1, e_ 1, w_ 1], [ s_ 2, e_ 2, w_ 2], ..., [ s_ n, e_ n, w_ n]}，其中s_ i < e_ i。找出一个子集S ⊆ I，使得对于任意两个不同区间i,j ∈ S，区间i和j不重叠（即e_ i ≤ s_ j 或 e_ j ≤ s_ i），并且∑w_ i (i∈S)达到最大值。 解题过程 步骤1：问题分析与预处理 首先我们需要对区间进行排序，这样便于后续处理。按照结束时间e_ i从小到大排序。这样当我们考虑第i个区间时，所有结束时间比它早的区间都已经处理过了。 排序后，我们需要找到"前一个不重叠的区间"。对于区间i，定义p(i)为最大的j < i，使得区间j的结束时间 ≤ 区间i的开始时间。如果不存在这样的区间，则p(i) = 0。 步骤2：定义状态 定义dp[ i ]表示考虑前i个区间（排序后的前i个）时，能获得的最大权重和。 步骤3：状态转移方程 对于每个区间i，我们有两种选择： 不选择区间i：那么最大权重就是dp[ i-1 ] 选择区间i：那么最大权重是w_ i + dp[ p(i) ]（选择当前区间，再加上在它之前且不重叠的区间的最大权重） 因此状态转移方程为： dp[ i] = max(dp[ i-1], w_ i + dp[ p(i) ]) 步骤4：边界条件 dp[ 0 ] = 0（没有区间时，权重和为0） 步骤5：计算p(i)数组 我们可以使用二分查找来高效计算p(i)。对于每个区间i，在排序后的区间数组中二分查找最大的j，使得e_ j ≤ s_ i。 步骤6：算法实现 对区间按结束时间排序 计算p(i)数组 初始化dp[ 0 ] = 0 对于i从1到n： dp[ i] = max(dp[ i-1], w_ i + dp[ p(i) ]) 最终答案为dp[ n ] 步骤7：时间复杂度分析 排序：O(n log n) 计算p(i)：n次二分查找，每次O(log n)，总共O(n log n) 动态规划：O(n) 总时间复杂度：O(n log n) 步骤8：构造最优解 如果我们还需要找出具体选择了哪些区间，可以反向追踪： 从i = n开始，如果dp[ i] > dp[ i-1 ]，说明选择了区间i，然后跳转到p(i)；否则不选择区间i，跳转到i-1。 这个算法通过巧妙的排序和动态规划，高效地解决了带权区间调度这一经典优化问题。