区间动态规划例题：区间覆盖问题（最小选择不相交区间使得覆盖指定连续范围）
字数 2153 2025-12-19 13:57:26

区间动态规划例题：区间覆盖问题（最小选择不相交区间使得覆盖指定连续范围）

一、题目描述

给定一个闭区间 [L, R] 作为目标覆盖范围，以及 n 个小区间 intervals[i] = [l_i, r_i]（每个小区间是 [L, R] 的子区间），你可以选择若干个小区间，要求这些小区间互不相交（即任意两个被选中的小区间没有重叠部分），并且它们的并集必须恰好覆盖整个 [L, R]（不能有未覆盖的空隙，也不能超出目标范围）。

请你计算：是否存在这样的选择方案？如果存在，最少需要多少个小区间？如果不存在，返回 -1。

示例

L = 1, R = 10
intervals = [[1,3], [2,4], [3,5], [4,6], [5,7], [6,8], [7,9], [8,10]]

可选方案：选择 [1,3], [3,5], [5,7], [7,9], [9,10]（注意最后一个区间题目未给出，所以此例中无法覆盖到 10）。
实际上若 intervals 中没有恰好相接的区间，则可能无解。
若将 intervals 改为包含 [1,3], [3,6], [6,10]，则最少需 3 个区间。

二、问题分析与建模

这个问题的核心：

  1. 小区间必须互不相交。
  2. 它们的并集必须覆盖 [L, R]，不能有空隙。

由于区间互不相交，且要覆盖连续范围，那么这些小区间必须首尾相接。
即：假设最终方案选择的区间按左端点排序为 [a_1,b_1], [a_2,b_2], …, [a_k,b_k]，则必须满足：

  • a_1 = L
  • b_k = R
  • a_{i+1} = b_i（一个区间的右端点等于下一个区间的左端点）

这样问题变为：
在给定区间集合中，找出一个区间链，从 L 开始，到 R 结束，相邻区间首尾严格相等，且使用的区间数最少。

三、动态规划状态定义

设 dp[i] 表示：覆盖从 L 到 i（i 是 [L, R] 内的一个整数点）的最少区间数。
注意：由于题目区间是闭区间且要求相接，我们只需要考虑整数端点（假设所有端点都是整数，或者我们可以离散化）。

初始状态：
dp[L] = 0（还没选任何区间时，覆盖到 L 点本身不需要区间）。

转移方程：
对于每个 i（从 L 到 R），我们想用小区间 [l, r] 来延伸覆盖范围：
如果 dp[l] 已经计算过，且 l 已经被覆盖（即 dp[l] ≠ INF），那么我们可以用 [l, r] 这个区间，将覆盖扩展到 r。
则：

dp[r] = min(dp[r], dp[l] + 1)

关键：必须满足 l 已经被覆盖，且区间 [l, r] 存在于给定的区间集合中。

四、状态转移的实现细节

  1. 将所有区间按左端点 l 分组，便于快速找到从某个 l 出发的所有区间。

  2. 初始化 dp 数组，dp[L] = 0，其余为 INF。

  3. 遍历 i 从 L 到 R：

    • 如果 dp[i] 不是 INF，说明 i 已经被覆盖。
    • 对于所有左端点等于 i 的区间 [i, r]，更新 dp[r] = min(dp[r], dp[i] + 1)。

  4. 最终答案：dp[R]（如果为 INF 则无解，返回 -1）。

五、举例演算

例：
L=1, R=10
intervals = [[1,3], [3,6], [6,10]]

  • 初始：dp[1]=0，其余 INF。
  • i=1：找到区间 [1,3] → dp[3] = min(INF, 0+1) = 1。
  • i=2：dp[2] 是 INF，跳过。
  • i=3：dp[3]=1，找到区间 [3,6] → dp[6] = min(INF, 1+1) = 2。
  • i=4,5 跳过（dp 为 INF）。
  • i=6：dp[6]=2，找到区间 [6,10] → dp[10] = min(INF, 2+1) = 3。
  • 最终 dp[10]=3，最少需 3 个区间。

六、为什么这是区间DP？

虽然这里 dp 的定义是以点为单位，但转移本质是：

  • 区间 [l, r] 作为一个“一步跳跃”，从状态 l 转移到状态 r。
  • 它要求区间之间严格首尾相接，所以覆盖的过程是区间逐段拼接。

更广义的区间DP形式可以定义 dp[a][b] 表示能否用若干给定区间覆盖 [a, b] 且区间互不相交，但那样复杂度更高。
当前解法可以看作一维DP，但它的“阶段”是按覆盖的右端点逐步推进，仍然属于区间覆盖类DP的经典思路。

七、时间与空间复杂度

  • 时间复杂度：O(R - L + m)，其中 m 是区间数量（每个区间用于一次转移）。
  • 空间复杂度：O(R - L + m)。

如果端点范围很大，可以先离散化所有端点，再用类似BFS的方式做转移（此时问题转化为在区间图上求从 L 到 R 的最短路径）。

八、总结

本题展示了区间覆盖问题的一个变种：

  • 要求不相交且严格首尾相接。
  • 通过一维DP，以右端点为状态，利用左端点已覆盖的条件进行转移。
  • 本质是在区间构造的“衔接图”中找最短路径。

这种方法可以扩展到区间带权（求最小总权覆盖）等问题，只需将 dp[i] + 1 改为 dp[i] + weight 即可。

区间动态规划例题：区间覆盖问题（最小选择不相交区间使得覆盖指定连续范围） 一、题目描述 给定一个闭区间 [L, R] 作为目标覆盖范围，以及 n 个小区间 intervals[i] = [l_i, r_i] （每个小区间是 [L, R] 的子区间），你可以选择若干个小区间，要求这些小区间 互不相交 （即任意两个被选中的小区间没有重叠部分），并且它们的并集必须 恰好覆盖 整个 [L, R] （不能有未覆盖的空隙，也不能超出目标范围）。 请你计算：是否存在这样的选择方案？如果存在，最少需要多少个小区间？如果不存在，返回 -1。 示例 可选方案：选择 [1,3], [3,5], [5,7], [7,9], [9,10] （注意最后一个区间题目未给出，所以此例中无法覆盖到 10）。 实际上若 intervals 中没有恰好相接的区间，则可能无解。 若将 intervals 改为包含 [1,3], [3,6], [6,10] ，则最少需 3 个区间。 二、问题分析与建模 这个问题的核心： 小区间必须互不相交。 它们的并集必须覆盖 [L, R] ，不能有空隙。 由于区间互不相交，且要覆盖连续范围，那么 这些小区间必须首尾相接 。 即：假设最终方案选择的区间按左端点排序为 [a_1,b_1], [a_2,b_2], …, [a_k,b_k] ，则必须满足： a_1 = L b_k = R a_{i+1} = b_i （一个区间的右端点等于下一个区间的左端点） 这样问题变为： 在给定区间集合中，找出一个 区间链 ，从 L 开始，到 R 结束，相邻区间首尾严格相等，且使用的区间数最少。 三、动态规划状态定义 设 dp[i] 表示：覆盖从 L 到 i （ i 是 [L, R] 内的一个整数点）的 最少区间数 。 注意：由于题目区间是闭区间且要求相接，我们只需要考虑整数端点（假设所有端点都是整数，或者我们可以离散化）。 初始状态： dp[L] = 0 （还没选任何区间时，覆盖到 L 点本身不需要区间）。 转移方程： 对于每个 i （从 L 到 R ），我们想用小区间 [l, r] 来延伸覆盖范围： 如果 dp[l] 已经计算过，且 l 已经被覆盖（即 dp[l] ≠ INF ），那么我们可以用 [l, r] 这个区间，将覆盖扩展到 r 。 则： 关键 ：必须满足 l 已经被覆盖，且区间 [l, r] 存在于给定的区间集合中。 四、状态转移的实现细节 将所有区间按左端点 l 分组，便于快速找到从某个 l 出发的所有区间。 初始化 dp 数组， dp[L] = 0 ，其余为 INF 。 遍历 i 从 L 到 R ： 如果 dp[i] 不是 INF ，说明 i 已经被覆盖。 对于所有左端点等于 i 的区间 [i, r] ，更新 dp[r] = min(dp[r], dp[i] + 1) 。 最终答案： dp[R] （如果为 INF 则无解，返回 -1）。 五、举例演算 例： L=1, R=10 intervals = [[1,3], [3,6], [6,10]] 初始： dp[1]=0 ，其余 INF。 i=1 ：找到区间 [1,3] → dp[3] = min(INF, 0+1) = 1 。 i=2 ： dp[2] 是 INF，跳过。 i=3 ： dp[3]=1 ，找到区间 [3,6] → dp[6] = min(INF, 1+1) = 2 。 i=4,5 跳过（dp 为 INF）。 i=6 ： dp[6]=2 ，找到区间 [6,10] → dp[10] = min(INF, 2+1) = 3 。 最终 dp[10]=3 ，最少需 3 个区间。 六、为什么这是区间DP？ 虽然这里 dp 的定义是以点为单位，但转移本质是： 区间 [l, r] 作为一个“一步跳跃”，从状态 l 转移到状态 r 。 它要求区间之间严格首尾相接，所以覆盖的过程是区间逐段拼接。 更广义的区间DP形式可以定义 dp[a][b] 表示能否用若干给定区间覆盖 [a, b] 且区间互不相交，但那样复杂度更高。 当前解法可以看作 一维DP ，但它的“阶段”是按覆盖的右端点逐步推进，仍然属于区间覆盖类DP的经典思路。 七、时间与空间复杂度 时间复杂度： O(R - L + m) ，其中 m 是区间数量（每个区间用于一次转移）。 空间复杂度： O(R - L + m) 。 如果端点范围很大，可以先离散化所有端点，再用类似BFS的方式做转移（此时问题转化为在区间图上求从 L 到 R 的最短路径）。 八、总结 本题展示了 区间覆盖 问题的一个变种： 要求不相交且严格首尾相接。 通过一维DP，以右端点为状态，利用左端点已覆盖的条件进行转移。 本质是在区间构造的“衔接图”中找最短路径。 这种方法可以扩展到区间带权（求最小总权覆盖）等问题，只需将 dp[i] + 1 改为 dp[i] + weight 即可。