“带权区间调度问题的变种：每个区间有一个执行概率，求期望最大收益”
字数 2446 2025-12-20 03:59:00

“带权区间调度问题的变种：每个区间有一个执行概率，求期望最大收益”

题目描述

给定一系列区间，每个区间有三个属性：

  • 开始时间 start_i
  • 结束时间 end_i（区间互不重叠且已按结束时间升序排列）
  • 收益 profit_i（执行该区间可获得的固定收益）
  • 执行概率 prob_i（区间被执行的可能性，0 ≤ prob_i ≤ 1）

当选择一个区间执行时，必须确保其不与已选择的区间重叠。如果某个区间未被选中，则收益为0。每个区间的执行独立于其他区间（即每个区间的执行是一个独立随机事件，不影响其他区间是否被选中）。目标是选择一组非重叠的区间，使得期望总收益最大。

解题思路

这个问题是带权区间调度问题（Weighted Interval Scheduling）的随机化扩展。
在原问题中，每个区间有固定收益，要求选择一组不重叠区间使收益最大，可以通过动态规划解决。
现在引入概率后，期望收益需要考虑每个区间是否被“选中执行”的随机性，同时需保证选择的区间集不重叠。

关键点：

  • 执行概率仅影响区间被“激活”时的收益期望，而不影响可行性约束。
  • 对于每个区间 i，其期望收益 = profit_i * prob_i。
  • 我们依然需要从排序后的区间中选择一个子集，保证不重叠。

因此，我们可以将期望收益视为新的权重，然后直接套用带权区间调度问题的标准动态规划解法。

步骤详解

1. 预处理与排序

区间已按结束时间 end_i 升序排列。
定义：

  • p[i]：在区间 i 之前且不与 i 重叠的最后一个区间的索引（若不存在则为 -1）。
    即：p[i] = max{ j | end_j ≤ start_i, j < i }，可通过二分查找快速求得。

2. 动态规划状态定义

设 dp[i] 表示考虑前 i 个区间（即区间 0 到 i-1）时，能获得的最大期望收益。
注意：区间索引从 0 开始，dp[0] = 0（无区间可选）。

3. 状态转移方程

对于每个区间 i-1（对应前 i 个区间中的最后一个区间）：

  • 选择区间 i-1：期望收益 = profit_{i-1} * prob_{i-1} + dp[p[i-1] + 1]
    （p[i-1] 是前一个不重叠的区间索引，+1 是因为 dp 的下标是“前 k 个区间”）
  • 不选择区间 i-1：收益 = dp[i-1]
  • 取最大值：
    dp[i] = max(dp[i-1], profit_{i-1} * prob_{i-1} + dp[p[i-1] + 1])

注意：这里 p[i-1] + 1 可能等于 i-1（如果 p[i-1] = i-2），但这是正确的，因为 dp 索引代表“前 k 个区间”。

4. 算法流程

  1. 输入 n 个区间，按 end_i 升序排列（假设已排序）。
  2. 计算 p[] 数组：对每个区间 i，二分查找最大的 j 使得 end_j ≤ start_i。
  3. 初始化 dp[0] = 0。
  4. 循环 i = 1 到 n：
    • val = profit[i-1] * prob[i-1]
    • prev = p[i-1]
    • dp[i] = max(dp[i-1], val + dp[prev + 1])
  5. 答案 = dp[n]。

5. 示例演算

假设有 3 个区间：

i start end profit prob
0 1 3 10 0.8
1 2 5 20 0.5
2 4 6 15 0.9

按 end 排序后顺序不变（因为已按 end 升序）。

计算 p[]：

  • p[0] = -1（前面没有不重叠的区间）
  • p[1]：区间 1 的 start=2，找 end ≤ 2 的区间 → 区间 0 的 end=3 > 2，无 → p[1] = -1
  • p[2]：区间 2 的 start=4，找 end ≤ 4 的区间 → 区间 1 的 end=5 > 4，区间 0 的 end=3 ≤ 4 → p[2] = 0

期望收益：

  • exp[0] = 10 * 0.8 = 8
  • exp[1] = 20 * 0.5 = 10
  • exp[2] = 15 * 0.9 = 13.5

DP 计算（dp[0]=0）：

  • i=1（区间0）：
    选择：8 + dp[-1+1] = 8 + dp[0] = 8
    不选：dp[0] = 0
    dp[1] = max(0, 8) = 8
  • i=2（区间1）：
    选择：10 + dp[-1+1] = 10 + dp[0] = 10
    不选：dp[1] = 8
    dp[2] = max(8, 10) = 10
  • i=3（区间2）：
    选择：13.5 + dp[0+1] = 13.5 + dp[1] = 13.5 + 8 = 21.5
    不选：dp[2] = 10
    dp[3] = max(10, 21.5) = 21.5

最大期望收益 = 21.5（选择区间 0 和区间 2）。

6. 算法复杂度

  • 排序：O(n log n)（如果未排序）。
  • 计算 p[]：对每个区间二分查找 O(n log n)。
  • DP 转移：O(n)。
    总复杂度 O(n log n)。

7. 关键理解

  • 这个变种巧妙地将随机性转化为期望权重，从而转化为确定性优化问题。
  • 每个区间是否执行只影响收益期望，不影响可行性，因此只需将原问题的权重替换为期望收益即可。
  • 如果概率为 1，则退化到经典带权区间调度问题。
“带权区间调度问题的变种：每个区间有一个执行概率，求期望最大收益” 题目描述 给定一系列区间，每个区间有三个属性： 开始时间 start_i 结束时间 end_i （区间互不重叠且已按结束时间升序排列） 收益 profit_i （执行该区间可获得的固定收益） 执行概率 prob_i （区间被执行的可能性，0 ≤ prob_i ≤ 1） 当选择一个区间执行时，必须确保其不与已选择的区间重叠。如果某个区间未被选中，则收益为0。每个区间的执行独立于其他区间（即每个区间的执行是一个独立随机事件，不影响其他区间是否被选中）。目标是选择一组 非重叠 的区间，使得 期望总收益 最大。 解题思路 这个问题是 带权区间调度问题 （Weighted Interval Scheduling）的 随机化扩展 。 在原问题中，每个区间有固定收益，要求选择一组不重叠区间使收益最大，可以通过动态规划解决。 现在引入 概率 后，期望收益需要考虑每个区间是否被“选中执行”的随机性，同时需保证选择的区间集不重叠。 关键点 ： 执行概率仅影响区间被“激活”时的收益期望，而不影响可行性约束。 对于每个区间 i ，其 期望收益 = profit_i * prob_i 。 我们依然需要从排序后的区间中选择一个子集，保证不重叠。 因此，我们可以将 期望收益 视为新的权重，然后直接套用带权区间调度问题的标准动态规划解法。 步骤详解 1. 预处理与排序 区间已按结束时间 end_i 升序排列。 定义： p[i] ：在区间 i 之前且不与 i 重叠的最后一个区间的索引（若不存在则为 -1）。 即： p[i] = max{ j | end_j ≤ start_i, j < i } ，可通过二分查找快速求得。 2. 动态规划状态定义 设 dp[i] 表示 考虑前 i 个区间（即区间 0 到 i-1）时，能获得的最大期望收益 。 注意：区间索引从 0 开始， dp[0] = 0 （无区间可选）。 3. 状态转移方程 对于每个区间 i-1 （对应前 i 个区间中的最后一个区间）： 选择区间 i-1 ：期望收益 = profit_{i-1} * prob_{i-1} + dp[p[i-1] + 1] （ p[i-1] 是前一个不重叠的区间索引， +1 是因为 dp 的下标是“前 k 个区间”） 不选择区间 i-1 ：收益 = dp[i-1] 取最大值： dp[i] = max(dp[i-1], profit_{i-1} * prob_{i-1} + dp[p[i-1] + 1]) 注意 ：这里 p[i-1] + 1 可能等于 i-1 （如果 p[i-1] = i-2 ），但这是正确的，因为 dp 索引代表“前 k 个区间”。 4. 算法流程 输入 n 个区间，按 end_i 升序排列（假设已排序）。 计算 p[] 数组：对每个区间 i ，二分查找最大的 j 使得 end_j ≤ start_i 。 初始化 dp[0] = 0 。 循环 i = 1 到 n ： val = profit[i-1] * prob[i-1] prev = p[i-1] dp[i] = max(dp[i-1], val + dp[prev + 1]) 答案 = dp[n] 。 5. 示例演算 假设有 3 个区间： | i | start | end | profit | prob | |---|-------|-----|--------|------| | 0 | 1 | 3 | 10 | 0.8 | | 1 | 2 | 5 | 20 | 0.5 | | 2 | 4 | 6 | 15 | 0.9 | 按 end 排序后顺序不变（因为已按 end 升序）。 计算 p[] ： p[0] = -1 （前面没有不重叠的区间） p[1] ：区间 1 的 start=2，找 end ≤ 2 的区间 → 区间 0 的 end=3 > 2，无 → p[1] = -1 p[2] ：区间 2 的 start=4，找 end ≤ 4 的区间 → 区间 1 的 end=5 > 4，区间 0 的 end=3 ≤ 4 → p[2] = 0 期望收益 ： exp[0] = 10 * 0.8 = 8 exp[1] = 20 * 0.5 = 10 exp[2] = 15 * 0.9 = 13.5 DP 计算 （ dp[0]=0 ）： i=1 （区间0）： 选择： 8 + dp[-1+1] = 8 + dp[0] = 8 不选： dp[0] = 0 dp[1] = max(0, 8) = 8 i=2 （区间1）： 选择： 10 + dp[-1+1] = 10 + dp[0] = 10 不选： dp[1] = 8 dp[2] = max(8, 10) = 10 i=3 （区间2）： 选择： 13.5 + dp[0+1] = 13.5 + dp[1] = 13.5 + 8 = 21.5 不选： dp[2] = 10 dp[3] = max(10, 21.5) = 21.5 最大期望收益 = 21.5 （选择区间 0 和区间 2）。 6. 算法复杂度 排序：O(n log n)（如果未排序）。 计算 p[] ：对每个区间二分查找 O(n log n)。 DP 转移：O(n)。 总复杂度 O(n log n) 。 7. 关键理解 这个变种巧妙地将 随机性 转化为 期望权重 ，从而转化为确定性优化问题。 每个区间是否执行只影响收益期望，不影响可行性，因此只需将原问题的权重替换为期望收益即可。 如果概率为 1，则退化到经典带权区间调度问题。