题目：带权区间调度问题（加权区间调度，Weighted Interval Scheduling） 题目描述 我们有 n 个区间，每个区间 i 包含开始时间 start[i] 、结束时间 end[i] 和对应的权重（价值） weight[i] 。目标是从这些区间中选出 一个子集 ，使得选中的区间 两两不重叠 （即任意两个区间在时间上不重叠），并且 所选区间的总权重之和最大 。注意，我们允许区间是离散的（比如任务调度），但更常见的是假设区间是连续的，因此一个区间的结束时间等于下一个区间的开始时间不算重叠（即如果 end[i] <= start[j] ，则区间 i 和 j 不重叠）。我们需要输出最大的总权重。 例如，假设有区间： 区间1: 开始=1, 结束=3, 权重=5 区间2: 开始=2, 结束=5, 权重=6 区间3: 开始=4, 结束=6, 权重=5 区间4: 开始=6, 结束=8, 权重=7 不重叠的子集可以是 {区间1, 区间4}，总权重=5+7=12；或者 {区间2, 区间4}，总权重=6+7=13。最大总权重是13。 解题步骤 这是一个经典的优化问题，可以用动态规划解决。关键思路是按照结束时间对所有区间排序，然后定义状态 dp[i] 表示“考虑前 i 个区间（按结束时间排序后），并且 必须选择第 i 个区间 时，能获得的最大总权重”。最终答案是所有 dp[i] 中的最大值（因为我们不一定非要选最后一个区间，但状态定义为“必须选第 i 个”，所以取所有 i 的最大值）。 第一步：预处理区间 将每个区间表示为一个三元组 (start, end, weight) 。 按照 结束时间 从小到大排序。如果结束时间相同，可以按开始时间排序（通常不影响结果）。排序的目的是为了能够快速找到“不冲突”的前驱区间。 为了方便，我们可以假设区间编号从 1 到 n（排序后），并添加一个虚拟区间0，其结束时间为负无穷，权重为0，这样简化边界。 第二步：定义状态 定义 dp[i] 为：以第 i 个区间 作为最后一个被选中的区间 时，能够获得的最大总权重。 注意，这个定义隐含了“前 i 个区间中，我们选了若干个，但最后一个一定是 i”。这样我们就可以利用不重叠性质，从前面某个不冲突的区间 j 转移过来。 第三步：找到“前驱”区间 对于每个区间 i，我们定义 p[i] 表示在区间 i 开始之前结束的、最后一个区间的索引。 形式化地说， p[i] 是满足 end[j] <= start[i] 的最大 j（j < i）。 为什么是最大的 j？因为我们按结束时间排序了，所以这样找到的 j 是与 i 不冲突的、结束时间最晚的区间。 我们可以用二分查找在排序后的区间数组中快速计算 p[i] 。 第四步：状态转移方程 对于区间 i，有两种选择： 不选任何前面的区间，只选 i 自己，总权重 = weight[i] 。 在选 i 之前，先选一个与 i 不冲突的区间 j，即 j = p[ i]，那么总权重 = dp[p[i]] + weight[i] 。 注意，因为 p[ i] 是与 i 不冲突的最后一个区间，所以 dp[ p[ i]] 已经是以 p[ i ] 结尾的最优解，再加上 i 是安全的。 那么状态转移方程是： dp[i] = max(weight[i], dp[p[i]] + weight[i]) 但更常见的是写成： dp[i] = weight[i] + (p[i] > 0 ? dp[p[i]] : 0) ，因为如果 p[ i ] = 0 表示前面没有不冲突区间。 第五步：计算最终答案 由于 dp[ i ] 表示“以 i 结尾”的最大权重，最终答案不一定要以最后一个区间结尾，所以答案是： ans = max(dp[1], dp[2], ..., dp[n]) 。 我们可以在计算 dp 数组的过程中维护一个全局最大值。 第六步：边界与初始化 我们可以令 dp[ 0 ] = 0 作为虚拟区间。 对于 i 从 1 到 n，先计算 p[ i]，然后 dp[i] = weight[i] + dp[p[i]] 。 最终答案 = max(dp)。 第七步：时间复杂度 排序 O(n log n)。 计算 p[ i ] 对每个 i 二分查找 O(n log n)。 DP 转移 O(n)。 总时间复杂度 O(n log n)，空间 O(n)。 第八步：举例验证 以开头的例子： 区间（已按结束时间排序）： 1: (1,3,5) 2: (2,5,6) 3: (4,6,5) 4: (6,8,7) 计算 p[ i ]： p[ 1 ] = 0（没有区间在时刻1之前结束） p[ 2]：start[ 2]=2，找 end <= 2 的最大 j，只有区间1的 end=3 > 2，所以 p[ 2 ]=0。 p[ 3]：start[ 3]=4，找 end <= 4 的最大 j，区间2的 end=5>4，区间1的 end=3<=4，所以 p[ 3 ]=1。 p[ 4]：start[ 4]=6，找 end <= 6 的最大 j，区间3的 end=6<=6，所以 p[ 4 ]=3。 现在计算 dp： dp[ 0 ]=0 dp[ 1] = 5 + dp[ 0 ] = 5 dp[ 2] = 6 + dp[ 0 ] = 6 dp[ 3] = 5 + dp[ 1 ] = 5+5=10 dp[ 4] = 7 + dp[ 3 ] = 7+10=17 最大值是 17？不对！检查一下：区间4 (6,8) 和区间3 (4,6) 是冲突的，因为区间3的结束时间6等于区间4的开始时间6，按照我们的定义（不重叠要求 end <= start），这是不重叠的，因为等于是允许的。但 dp[ 4] 选择了区间3，区间3又选了区间1，总区间是 {1,3,4}，检查是否重叠：区间1 (1,3) 与区间3 (4,6) 不重叠（3 <= 4），区间3 (4,6) 与区间4 (6,8) 不重叠（6 <= 6）。所以三个区间都可以选，总权重=5+5+7=17。但看原题区间3权重=5，我们算出来是17，看起来对。但最初我们手算最大是13，为什么？因为我们最初手算时漏掉了 {区间1, 区间3, 区间4} 这个组合。验证：区间1 (1,3), 区间3 (4,6), 区间4 (6,8) 的确都不重叠，总权重=5+5+7=17，比13大。所以 DP 给了正确解 17。 第九步：如何输出所选区间？ 如果需要输出具体区间，我们可以用额外的数组 prev[i] 记录 dp[ i] 是从哪个前驱转移来的（即 p[ i] 或 0）。然后从最大的 dp[ i ] 对应的 i 开始，往回跳转到前驱，直到 0，收集区间编号即可。 第十步：思考 这个问题的核心是排序后定义“以 i 结尾”的状态，利用 p[ i ] 快速找到不冲突的前驱，从而将问题转化为类似“最长递增子序列”的 DP，但加上了权重。这是一种典型的“区间选择+权重最大化”的动态规划模型。