带权区间图的最小着色成本问题

问题描述

给定一个带权区间图（每个区间有权重），以及一个颜色集合，每种颜色有一个使用成本。要求为每个区间分配一种颜色，使得任意两个重叠的区间颜色不同，且总成本（每个区间的权重乘以其颜色的成本）最小。

输入：

• intervals：区间列表，每个区间为 [start, end, weight]
• colors：颜色成本列表，colors[i] 表示第 i 种颜色的使用成本
  输出：最小总成本。若无法完成着色（颜色数不足），返回 -1。

关键思路

1. 区间排序与预处理

   • 按区间右端点排序，便于判断重叠关系。
   • 预处理每个区间左侧最近的不重叠区间（类似会议安排问题），记录为 prev[i]。

2. 状态定义

   • 设 dp[i][c] 表示前 i 个区间中，第 i 个区间使用颜色 c 时的最小总成本。
   • 由于颜色限制来自重叠区间，需考虑前一个不重叠区间的颜色选择。

3. 状态转移

   • 若区间 i 使用颜色 c，则前一个与 i 重叠的区间不能使用 c，但更早的区间可复用 c。
   • 通过 prev[i] 快速定位需要比较颜色的区间。

详细步骤

步骤 1：排序与预处理

• 将区间按右端点升序排序，记录原始索引（因需输出方案时使用）。
• 计算 prev[i]：对区间 i，找到最后一个右端点 ≤ 其左端点的区间 j，若不存在则 prev[i] = -1。

  # 示例：intervals = [[1,3,2], [2,4,1], [3,5,3]]
  # 排序后：[[1,3,2], [2,4,1], [3,5,3]]
  # prev[0] = -1（左侧无区间）
  # prev[1] = -1（与区间0重叠）
  # prev[2] = 0? 检查：区间2左端=3，区间0右端=3，不重叠？需严格小于：左端 > 前区间右端
  # 正确规则：prev[i] = 最大的 j 满足 right_j < left_i
  

步骤 2：动态规划定义

• 设 dp[i][c]：前 i 个区间（排序后），且第 i 个区间使用颜色 c 时的最小成本。
• 初始化：dp[0][c] = weight[0] * color_cost[c]。

步骤 3：状态转移方程

• 对于区间 i 和颜色 c：
  1. 找到前一个不重叠区间 p = prev[i]。
  2. 如果 p == -1（左侧无区间），则成本 = weight[i] * color_cost[c]。
  3. 如果 p != -1，需枚举区间 p 的颜色 k（k ≠ c），取最小成本：

     dp[i][c] = min_over_k≠c { dp[p][k] } + weight[i] * color_cost[c]
     

  4. 但注意：可能多个区间介于 p 和 i 之间，它们与 i 重叠，但彼此不重叠？
     • 实际上，由于按右端点排序，区间 i 只与右端点 ≥ 其左端点的区间重叠。
     • 因此，只需保证与 i 重叠的最近区间（即最后一个与 i 重叠的区间）颜色不同。
     • 但更早的区间可能也与 i 重叠？ 是的！所以需检查所有与 i 重叠的区间都不使用 c。
     • 但这样复杂度高。优化：用前缀最小值数组避免枚举 p 的颜色。

步骤 4：优化转移

• 维护 min_dp[i] 表示 min(dp[i][所有c])。
• 对于区间 i：
  • 枚举颜色 c：
    • 找到最后一个与 i 重叠的区间 j（即右端点 ≥ left_i 的最后一个区间）。
    • 设 p = prev[i]（最后一个不重叠的）。
    • 如果存在重叠区间 j，则需保证 j 的颜色 ≠ c。但 j 可能不是 p？
      • 实际上，所有与 i 重叠的区间在排序后是连续的，且最后一个重叠区间是 i-1？ 不一定。
      • 正确方法：线段树或前缀数组维护颜色最小值，跳过重叠区间的颜色 c。

简化版解法（实用）：

• 按右端点排序后，对每个区间 i，枚举其颜色 c。
• 找到最后一个与 i 重叠的区间 j（即最大 j < i 且 right_j ≥ left_i）。
• 如果不存在 j，则 dp[i][c] = weight[i] * color_cost[c]。
• 如果存在 j，则需枚举 j 的颜色 k（k ≠ c），取 dp[j][k] 的最小值，加上当前成本。
• 但 j 可能多个？ 实际上，只需考虑最后一个重叠区间 j，因为更早的重叠区间会被 j 约束（j 与它们重叠，颜色已不同）。

最终转移方程：

dp[i][c] = min{
    min_over_k≠c { dp[j][k] },   // j 是最后一个与 i 重叠的区间
    min_over_all colors { dp[p][k] }  // p 是最后一个不重叠的区间（若 j 不存在则 p 生效）
} + weight[i] * color_cost[c]

实际可合并：若 j 存在，则 p 是 j 的前一个不重叠区间？ 不，j 与 i 重叠，p 是 i 的不重叠前驱。
更准确：

• 设 last_overlap[i] = 最大的 j < i 且 right_j ≥ left_i（即最后一个重叠区间）。
• 若 last_overlap[i] 不存在，则成本 = min_over_all colors { dp[p][k] }（若 p 存在）或直接当前成本（若 p 不存在）。
• 但通常 last_overlap[i] 存在时，需保证该区间颜色 ≠ c，因此取 min_over_k≠c { dp[last_overlap[i]][k] }。

算法实现（伪代码）

1. 排序区间按右端点。
2. 计算 last_overlap[i] 和 prev[i]。
3. 初始化 dp 为无穷大。
4. 对于 i = 0 到 n-1：
   • 对于颜色 c：
     • 如果 last_overlap[i] 存在：
       • 取 min_{k≠c} dp[last_overlap[i]][k] 作为基础值。
     • 否则如果 prev[i] 存在：
       • 取 min_{all k} dp[prev[i]][k]。
     • 否则基础值 = 0。
     • dp[i][c] = 基础值 + weight[i] * color_cost[c]。
5. 答案 = min_{c} dp[n-1][c]，若无穷大则返回 -1。

示例

区间：[[1,3,2], [2,4,1], [3,5,3]]
颜色成本：[1, 2]（两种颜色）
排序后同。

• i=0: last_overlap=-1, prev=-1 → dp[0][0]=21=2, dp[0][1]=22=4。
• i=1: 左端=2，last_overlap=0（区间0右端=3≥2），prev=-1。
  • c=0: min_{k≠0} dp[0][k]=dp[0][1]=4 → dp[1][0]=4+1*1=5。
  • c=1: min_{k≠1} dp[0][k]=dp[0][0]=2 → dp[1][1]=2+1*2=4。
• i=2: 左端=3，last_overlap=1（区间1右端=4≥3），prev=0（区间0右端=3<3？不，应严格小于：右端<左端→区间0右端=3不小于3，所以prev=-1？）
  正确：prev[i] 是最大 j 满足 right_j < left_i。左端=3，区间0右端=3不<3，区间1右端=4不<3，故 prev=-1。
  • c=0: min_{k≠0} dp[1][k]=dp[1][1]=4 → dp[2][0]=4+3*1=7。
  • c=1: min_{k≠1} dp[1][k]=dp[1][0]=5 → dp[2][1]=5+3*2=11。
    答案 = min(7,11)=7。

复杂度

• 时间：O(n * m^2)（m 为颜色数），优化后 O(n*m)。
• 空间：O(n*m)。

此问题结合了区间调度与着色约束，是区间动态规划的典型应用。