带权区间调度问题（Weighted Interval Scheduling） 问题描述 给定一组区间，每个区间有一个开始时间、结束时间和权重。目标是选择一组互不重叠的区间，使得这些区间的权重之和最大。与经典区间调度不同，这里每个区间有权重，我们需要最大化总权重而非区间数量。 解题思路 首先按结束时间对区间排序，便于判断是否重叠 定义dp[ i ]表示考虑前i个区间时能获得的最大权重和 对于每个区间i，有两种选择：不选它（继承dp[ i-1 ]）或选它（权重加上它之前第一个不重叠的区间的dp值） 关键是如何快速找到"之前第一个不重叠的区间" 详细步骤 步骤1：预处理排序 将区间按结束时间从小到大排序。这样保证在考虑区间i时，所有结束时间≤i的区间都已经处理过。 示例：假设有区间数据： 区间1: [ 1,3 ] 权重=5 区间2: [ 2,5 ] 权重=6 区间3: [ 4,6 ] 权重=3 区间4: [ 3,7 ] 权重=8 排序后：区间1→区间2→区间3→区间4 步骤2：定义状态 dp[ i ] = 考虑前i个区间（按结束时间排序）时能获得的最大权重和 步骤3：状态转移方程 对于第i个区间： 不选第i个区间：dp[ i] = dp[ i-1 ] 选第i个区间：dp[ i] = weight[ i] + dp[ p(i) ] 其中p(i)是最后一个结束时间≤第i个区间开始时间的区间编号 步骤4：寻找p(i)的方法 由于区间已按结束时间排序，可以用二分查找快速找到p(i)： 在区间1到i-1中，找到最大的j使得end[ j] ≤ start[ i ] 步骤5：算法实现 按结束时间排序区间 初始化dp[ 0 ] = 0 对于i从1到n： 用二分查找找到p(i) dp[ i] = max(dp[ i-1], weight[ i] + dp[ p(i) ]) 答案为dp[ n ] 步骤6：时间复杂度分析 排序：O(n log n) n次二分查找：O(n log n) 总复杂度：O(n log n) 步骤7：构造最优解 通过记录选择情况可以回溯出具体选择了哪些区间： 如果dp[ i] == dp[ i-1 ]，说明没选区间i 如果dp[ i] == weight[ i] + dp[ p(i) ]，说明选了区间i，然后跳到p(i)继续回溯 这种算法高效地解决了带权区间调度问题，通过动态规划+二分查找达到了最优解。