带权重的区间调度问题

字数 1904 2025-12-06 08:16:10

带权重的区间调度问题

题目描述
给定一系列任务，每个任务 i 有一个开始时间 start[i]、结束时间 end[i] 和权重（价值）weight[i]。这些任务都安排在同一条时间线上，且同一时间只能进行一个任务。目标是选择一个不重叠的任务子集，使得子集中所有任务的权重之和最大。注意：任务一旦被选中，必须完整执行，且一个任务结束时，另一个任务可以立即开始（即结束时间等于另一个任务的开始时间，不视为重叠）。

解题过程
这是一个经典的区间调度问题，可以使用动态规划来高效求解。以下是详细步骤：

排序
为了方便处理，首先将所有任务按照结束时间 end[i] 升序排序。如果结束时间相同，可以按开始时间升序排序，但这通常不影响核心逻辑。排序后，任务的索引顺序就固定了。
定义DP状态
设 dp[i] 表示考虑前 i 个任务（排序后的任务0到i-1）时，能获得的最大权重和。
另一种常见定义是：dp[i] 表示“必须选择第 i 个任务”时的最大权重和。但这里采用前一种定义，因为它更直观，最后答案就是 dp[n]。
状态转移
对于每个任务 i（排序后的索引），我们有两种选择：
- 不选任务 i：那么最大权重和就是 dp[i-1]。
- 选任务 i：那么需要找到“最后一个不与任务 i 重叠的任务” j。即满足 end[j] <= start[i] 的最大 j。由于任务已按结束时间排序，可以通过二分查找快速找到 j。此时，最大权重和为 dp[j+1] + weight[i]（因为 j 是从0开始的索引，dp索引通常从1开始，注意调整）。
  综合，状态转移方程为：
  dp[i] = max(dp[i-1], dp[p(i)] + weight[i])
  其中 p(i) 表示最后一个不与任务 i 重叠的任务的索引（从0开始），如果不存在则为 -1，dp[0] 通常初始化为0。
具体计算步骤
a. 对任务数组按结束时间排序。
b. 预处理 p[i] 数组：对每个任务 i，在排序后的任务列表中，用二分查找找到最大的 j 使得 end[j] <= start[i]，将 p[i] = j，如果找不到则 p[i] = -1。
c. 初始化 dp[0] = 0（没有任务时权重和为0）。
d. 循环 i 从1到n（n为任务总数），dp[i] = max(dp[i-1], dp[p[i-1]+1] + weight[i-1])。注意索引偏移：任务 i-1 对应排序后的第 i-1 个任务，p[i-1] 是对它的预处理结果。
e. 最终答案为 dp[n]。
示例
假设有任务：
任务0: start=1, end=3, weight=5
任务1: start=2, end=5, weight=6
任务2: start=4, end=6, weight=5
任务3: start=6, end=7, weight=4
按结束时间排序后顺序为：任务0(1,3,5), 任务1(2,5,6), 任务2(4,6,5), 任务3(6,7,4)。
- 预处理 p: p[0]=-1, p[1]=0（因为任务1的start=2，最后一个结束时间≤2的是任务0）, p[2]=0（任务2的start=4，任务0结束3≤4）, p[3]=2（任务3的start=6，任务2结束6≤6）。
- DP计算：
  dp[0]=0
  i=1（任务0）: dp[1]=max(dp[0], dp[-1+1]+5)=max(0,0+5)=5
  i=2（任务1）: dp[2]=max(dp[1], dp[p[1]+1]+6)=max(5, dp[0+1]+6)=max(5,5+6)=11
  i=3（任务2）: dp[3]=max(dp[2], dp[p[2]+1]+5)=max(11, dp[0+1]+5)=max(11,5+5)=11
  i=4（任务3）: dp[4]=max(dp[3], dp[p[3]+1]+4)=max(11, dp[2+1]+4)=max(11,11+4)=15
- 结果：最大权重和为15（选择任务0、任务2、任务3）。
复杂度分析
- 排序：O(n log n)
- 预处理p：每个任务二分查找 O(log n)，总 O(n log n)
- DP计算：O(n)
  总时间复杂度 O(n log n)，空间复杂度 O(n)。

这个解法保证了在任务不重叠的条件下最大化总权重，适用于任务调度、资源分配等场景。

带权重的区间调度问题题目描述给定一系列任务，每个任务 i 有一个开始时间 start[i] 、结束时间 end[i] 和权重（价值） weight[i] 。这些任务都安排在同一条时间线上，且同一时间只能进行一个任务。目标是选择一个不重叠的任务子集，使得子集中所有任务的权重之和最大。注意：任务一旦被选中，必须完整执行，且一个任务结束时，另一个任务可以立即开始（即结束时间等于另一个任务的开始时间，不视为重叠）。解题过程这是一个经典的区间调度问题，可以使用动态规划来高效求解。以下是详细步骤：排序为了方便处理，首先将所有任务按照结束时间 end[i] 升序排序。如果结束时间相同，可以按开始时间升序排序，但这通常不影响核心逻辑。排序后，任务的索引顺序就固定了。定义DP状态设 dp[i] 表示考虑前 i 个任务（排序后的任务0到i-1）时，能获得的最大权重和。另一种常见定义是： dp[i] 表示“必须选择第 i 个任务”时的最大权重和。但这里采用前一种定义，因为它更直观，最后答案就是 dp[n] 。状态转移对于每个任务 i（排序后的索引），我们有两种选择：不选任务 i：那么最大权重和就是 dp[i-1] 。选任务 i：那么需要找到“最后一个不与任务 i 重叠的任务” j。即满足 end[j] <= start[i] 的最大 j。由于任务已按结束时间排序，可以通过二分查找快速找到 j。此时，最大权重和为 dp[j+1] + weight[i] （因为 j 是从0开始的索引，dp索引通常从1开始，注意调整）。综合，状态转移方程为： dp[i] = max(dp[i-1], dp[p(i)] + weight[i]) 其中 p(i) 表示最后一个不与任务 i 重叠的任务的索引（从0开始），如果不存在则为 -1， dp[0] 通常初始化为0。具体计算步骤 a. 对任务数组按结束时间排序。 b. 预处理 p[i] 数组：对每个任务 i，在排序后的任务列表中，用二分查找找到最大的 j 使得 end[j] <= start[i] ，将 p[i] = j ，如果找不到则 p[i] = -1 。 c. 初始化 dp[0] = 0 （没有任务时权重和为0）。 d. 循环 i 从1到n（n为任务总数）， dp[i] = max(dp[i-1], dp[p[i-1]+1] + weight[i-1]) 。注意索引偏移：任务 i-1 对应排序后的第 i-1 个任务， p[i-1] 是对它的预处理结果。 e. 最终答案为 dp[n] 。示例假设有任务：任务0: start=1, end=3, weight=5 任务1: start=2, end=5, weight=6 任务2: start=4, end=6, weight=5 任务3: start=6, end=7, weight=4 按结束时间排序后顺序为：任务0(1,3,5), 任务1(2,5,6), 任务2(4,6,5), 任务3(6,7,4)。预处理 p: p[ 0]=-1, p[ 1]=0（因为任务1的start=2，最后一个结束时间≤2的是任务0）, p[ 2]=0（任务2的start=4，任务0结束3≤4）, p[ 3 ]=2（任务3的start=6，任务2结束6≤6）。 DP计算： dp[ 0 ]=0 i=1（任务0）: dp[ 1]=max(dp[ 0], dp[ -1+1 ]+5)=max(0,0+5)=5 i=2（任务1）: dp[ 2]=max(dp[ 1], dp[ p[ 1]+1]+6)=max(5, dp[ 0+1 ]+6)=max(5,5+6)=11 i=3（任务2）: dp[ 3]=max(dp[ 2], dp[ p[ 2]+1]+5)=max(11, dp[ 0+1 ]+5)=max(11,5+5)=11 i=4（任务3）: dp[ 4]=max(dp[ 3], dp[ p[ 3]+1]+4)=max(11, dp[ 2+1 ]+4)=max(11,11+4)=15 结果：最大权重和为15（选择任务0、任务2、任务3）。复杂度分析排序：O(n log n) 预处理p：每个任务二分查找 O(log n)，总 O(n log n) DP计算：O(n) 总时间复杂度 O(n log n)，空间复杂度 O(n)。这个解法保证了在任务不重叠的条件下最大化总权重，适用于任务调度、资源分配等场景。