带权区间调度问题 题目描述 给定n个区间，每个区间有一个开始时间s_ i、结束时间e_ i和权重w_ i。你的目标是选择一组互不重叠的区间，使得这些区间的总权重最大化。区间i和j互不重叠意味着e_ i ≤ s_ j或e_ j ≤ s_ i。 解题过程 步骤1：问题分析 这是一个典型的区间调度问题，与普通区间调度不同的是，每个区间都有权重，我们的目标不是最大化区间数量，而是最大化权重和。这需要动态规划来解决。 步骤2：数据预处理 首先按结束时间对所有区间进行排序： 将区间按结束时间e_ i从小到大排序 这样我们可以按顺序处理区间，便于找到不重叠的前驱区间 步骤3：定义状态 定义dp[ i ]：考虑前i个区间（按结束时间排序后），且必须选择第i个区间时，能获得的最大权重和。 步骤4：状态转移方程 对于每个区间i，我们有两种选择： 不选区间i：那么dp[ i ] = 0（但根据定义我们必须选i） 选区间i：需要找到前一个不重叠的区间j 更精确地说：dp[ i] = w_ i + max{0, dp[ j]}，其中j是满足e_ j ≤ s_ i的最大索引的区间。 步骤5：寻找前驱区间 对于每个区间i，我们需要快速找到最后一个结束时间小于等于s_ i的区间j。这可以用二分查找实现： 由于区间已按结束时间排序，我们可以二分查找满足e_ j ≤ s_ i的最大j 步骤6：算法实现 对区间按结束时间排序 初始化dp数组，大小为n 对于每个i从0到n-1： 用二分查找找到p(i)：最后一个结束时间≤s_ i的区间索引 如果存在p(i)：dp[ i] = w_ i + dp[ p(i) ] 否则：dp[ i] = w_ i 最终答案是max{dp[ 0], dp[ 1], ..., dp[ n-1 ]} 步骤7：时间复杂度分析 排序：O(n log n) n次二分查找：O(n log n) 总时间复杂度：O(n log n) 步骤8：示例演示 考虑区间：[ (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) 计算过程： dp[ 0 ] = 5（选择区间1） 区间2：前驱是None，dp[ 1 ] = 6 区间3：前驱是区间1，dp[ 2 ] = 5 + 5 = 10 区间4：前驱是区间3，dp[ 3 ] = 4 + 10 = 14 最大权重和为14（选择区间1、3、4） 步骤9：算法优化 我们可以用前缀最大值优化： 定义maxDP[ i] = max{dp[ 0], dp[ 1], ..., dp[ i ]} 这样在计算dp[ i]时，可以直接用maxDP[ p(i) ]而不用二分查找具体是哪个前驱区间 这个算法能高效解决带权区间调度问题，在实际应用中广泛使用。