带权重的区间调度问题（最大化总权重，区间不重叠）

题目描述：
给定 n 个区间，每个区间 i 由起始时间 start_i、结束时间 end_i 和权重 weight_i 表示。你需要选择若干个区间，使得任意两个被选区间都不重叠（端点可以相接），并且所有选中区间的权重之和最大。求这个最大总权重。

示例：

区间：[[1, 3, 5], [2, 5, 6], [4, 6, 5], [6, 7, 4], [5, 8, 11], [7, 9, 2]]
解释：每个区间是 [开始时间, 结束时间, 权重]

一种最优选择是 [1,3,5]、[4,6,5]、[7,9,2]，总权重为 5+5+2 = 12。
另一种选择是 [2,5,6] 和 [5,8,11]（注意 end=5 和 start=5 不重叠），总权重为 6+11 = 17，这比 12 更大。因此正确答案是 17。

解题思路

这是一个经典的加权区间调度问题，可以用动态规划解决。
核心思路是：

1. 排序：将所有区间按照结束时间从小到大排序。
2. 定义状态：设 dp[i] 表示考虑前 i 个区间（按结束时间排序后），并且必须选择第 i 个区间时，能获得的最大权重。
3. 状态转移：对于区间 i，我们有两种选择：
   • 只选区间 i，权重为 weight[i]。
   • 在区间 i 之前，选择一个不与区间 i 重叠的区间 j（即 end[j] <= start[i]），然后加上区间 i 的权重，即 dp[j] + weight[i]。
     因此转移方程为：

   dp[i] = weight[i] + max{ dp[j] | end[j] <= start[i] }
   

   其中 j 是所有满足条件的区间编号。
4. 最终答案：因为 dp[i] 表示必须选第 i 个区间，所以答案是 max(dp[1], dp[2], ..., dp[n])。

为了快速找到满足 end[j] <= start[i] 的最大 j，可以在排序后对每个区间 i 二分查找最后一个结束时间 ≤ start[i] 的区间下标 p[i]，则：

dp[i] = weight[i] + (p[i] == -1 ? 0 : dp[p[i]])

这里 p[i] = -1 表示没有这样的区间。

逐步推导

假设输入区间为：

区间0: [1,3,5]
区间1: [2,5,6]
区间2: [4,6,5]
区间3: [6,7,4]
区间4: [5,8,11]
区间5: [7,9,2]

第1步：按结束时间排序（如果结束时间相同，可以按开始时间排序，但不影响结果）：
排序后：

索引: 区间
0: [1,3,5]
1: [2,5,6]
2: [4,6,5]
3: [6,7,4]
4: [5,8,11]
5: [7,9,2]

这里结束时间已经是升序：3,5,6,7,8,9。

第2步：计算 p[i]（对于每个区间 i，找到最后一个结束时间 ≤ start[i] 的区间下标）：

• i=0, start=1：找不到结束时间 ≤1 的区间 → p[0] = -1。
• i=1, start=2：找结束时间 ≤2 的区间，区间0结束时间=3>2，没有 → p[1] = -1。
• i=2, start=4：找结束时间 ≤4 的区间，区间1结束时间=5>4，区间0结束时间=3≤4 → 最后一个满足的是区间0 → p[2] = 0。
• i=3, start=6：找结束时间 ≤6 的区间，区间2结束时间=6≤6 → p[3] = 2。
• i=4, start=5：找结束时间 ≤5 的区间，区间1结束时间=5≤5 → p[4] = 1。
• i=5, start=7：找结束时间 ≤7 的区间，区间3结束时间=7≤7 → p[5] = 3。

第3步：动态规划计算 dp[i]：

• dp[0] = weight[0] + (p[0]==-1?0:dp[p[0]]) = 5 + 0 = 5。
• dp[1] = 6 + 0 = 6。
• dp[2] = 5 + dp[0] = 5 + 5 = 10。
• dp[3] = 4 + dp[2] = 4 + 10 = 14。
• dp[4] = 11 + dp[1] = 11 + 6 = 17。
• dp[5] = 2 + dp[3] = 2 + 14 = 16。

第4步：取最大值：
max(5,6,10,14,17,16) = 17。

因此，最大总权重为 17，对应的选择是：区间1 ([2,5,6]) 和区间4 ([5,8,11])。

算法复杂度

• 排序：O(n log n)。
• 计算 p[i]：对每个 i 二分查找，O(n log n)。
• 动态规划：O(n)。
• 总复杂度：O(n log n)。

为什么这是区间动态规划？

虽然这个问题通常被归类为序列型动态规划，但它本质上涉及区间选择与重叠判断，状态 dp[i] 依赖于前面区间的结束时间与当前区间开始时间的关系，具有“区间决策”的特征。其动态规划的状态转移是基于区间之间的相容性（不重叠），因此可视为区间DP的一种简化形式（一维区间选择问题）。