带权重的区间调度问题（最大化总权重，区间不重叠）
题目描述
给定一系列工作，每个工作有开始时间 start[i]``、结束时间 end[i]和权重profit[i]`，表示完成这个工作能获得的收益。你希望选择一组不重叠的工作（即任意两个被选工作的时间段不重叠），使得这些工作的总权重（总收益）最大。请返回最大总收益。
示例：
输入：start = [1,2,3,3], end = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：选择工作0（收益50）和工作3（收益70），总收益120，它们的时间段 [1,3) 和 [3,6) 不重叠。
解题思路讲解
这个问题是经典“区间调度”的带权版本。如果我们只要求数量最多，可以用贪心（按结束时间排序，选最早结束且不冲突的），但这里每个工作权重不同，贪心可能不是最优，所以需要用动态规划。
第一步：问题分析与预处理
-
状态定义
我们需要考虑按某种顺序处理工作。一个自然的想法是：将工作按结束时间排序，这样当我们决定是否做某个工作时，只需要关心在它之前结束的工作。
定义dp[i]表示考虑前i个工作（按结束时间排序后），并且一定选择第 i 个工作时，能获得的最大收益。
但这样定义不方便直接递推，因为“选择第 i 个工作”意味着我们不能选任何与它时间重叠的工作。更常用的定义是：
dp[i]表示考虑前i个工作（排序后），能获得的最大收益（不一定要选第 i 个）。
这样，对于第 i 个工作，有两种选择：- 不选它：
dp[i] = dp[i-1] - 选它：收益是
profit[i] + dp[p(i)]，其中p(i)是在第 i 个工作开始之前结束的最后一个工作的下标（即不冲突的前一个工作）。
所以：
dp[i] = max(dp[i-1], profit[i] + dp[p(i)]) - 不选它：
-
排序与 p(i) 的计算
我们先创建一个工作列表，每个工作包括 (start, end, profit)，然后按 end 升序排序。
对于每个 i，我们需要找到最大的 j 满足end[j] <= start[i]。因为数组已按 end 排序，所以可以用二分查找快速得到 p(i)。
第二步：详细递推过程
假设有 n 个工作，排序后编号 0 到 n-1。
我们定义 dp[0] = profit[0]（只有一个工作时，最大收益就是选它）。
对于 i >= 1：
- 找到 p(i) 使得
end[p(i)] <= start[i]且 p(i) 尽可能大。如果找不到，记 p(i) = -1。 - 选择 i 的收益 =
profit[i] + (p(i) >= 0 ? dp[p(i)] : 0) - 不选 i 的收益 =
dp[i-1] dp[i] = max(选 i 的收益, 不选 i 的收益)
最终答案 = dp[n-1]。
第三步：示例推演
输入：start = [1,2,3,3], end = [3,4,5,6], profit = [50,10,40,70]
排序（按 end）：
工作0: (1,3,50)
工作1: (2,4,10)
工作2: (3,5,40)
工作3: (3,6,70)
计算 p(i)：
- i=0: start[0]=1，找 end <= 1 的工作，没有 → p(0) = -1
- i=1: start[1]=2，找 end <= 2 的工作，没有 → p(1) = -1
- i=2: start[2]=3，找 end <= 3 的工作，工作0的 end=3 满足 → p(2) = 0
- i=3: start[3]=3，找 end <= 3 的工作，工作0满足 → p(3) = 0
dp 计算：
- dp[0] = profit[0] = 50
- i=1: 选 = 10 + 0 = 10，不选 = 50 → dp[1] = 50
- i=2: 选 = 40 + dp[0] = 40+50=90，不选 = dp[1]=50 → dp[2] = 90
- i=3: 选 = 70 + dp[0] = 70+50=120，不选 = dp[2]=90 → dp[3] = 120
答案 = 120。
第四步：算法复杂度
排序 O(n log n)，计算每个 p(i) 二分查找 O(log n)，总 O(n log n)。空间 O(n) 存 dp。
第五步：关键点总结
- 按结束时间排序，保证“前面”的工作不会与当前工作冲突（如果结束时间 ≤ 开始时间）。
- 状态定义为“考虑前 i 个工作的最大收益”，决策是选或不选当前工作。
- 选当前工作时，收益要加上它之前最后一个不冲突工作的 dp 值，这体现了“不重叠”约束。
这样，我们通过排序 + 二分 + 动态规划，解决了带权区间调度的最大化收益问题。