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

字数 12243 2025-12-20 19:18:37

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

1. 题目描述

你获得一个闭区间的集合 intervals，其中每个区间形如 [start_i, end_i]（满足 0 <= start_i <= end_i <= n）。同时，你被给定一个目标区间 [targetStart, targetEnd]。你需要从 intervals 中选择一个子集，使得这些区间互不相交（即，任意两个被选中的区间都没有重叠，即使只在端点重叠也不允许），并且它们的并集能够完全覆盖目标区间 [targetStart, targetEnd]（即，目标区间内的每个点都必须被至少一个所选区间覆盖）。问：至少需要选择多少个区间才能满足条件？如果无法覆盖目标区间，则返回 -1。

示例
输入：
intervals = [[1,3], [2,4], [3,5], [4,6]], targetStart = 1, targetEnd = 6
输出：
2
解释：
我们可以选择区间 [1,3] 和 [4,6]。这两个区间互不相交，并且它们的并集覆盖了 [1,6]。注意，我们不能选择 [1,3] 和 [3,5]，因为它们在点 3 处重叠（题目要求不相交，即端点也不能重叠）。

数据范围

区间个数 m 最多为 1000。
所有区间的端点和目标区间的端点都在 [0, n] 范围内，n 最大为 10000。

2. 解题思路

这是一个区间选择与覆盖问题，由于需要满足“所选区间互不相交”且“完全覆盖一个连续的目标区间”，我们可以将问题转化为在给定的区间集合中，寻找一条从目标起点到目标终点的、由不重叠区间“拼接”而成的路径。这很适合用区间动态规划来求解，其中状态通常定义为“覆盖某个连续区间的最小代价（这里是最小区间数）”。

关键观察：

因为要求所选区间互不相交，所以如果我们按照区间的起点（或终点）排序，可以更方便地判断它们是否可能相邻。
为了用动态规划覆盖从 targetStart 到 targetEnd 的连续范围，我们可以定义状态 dp[l][r] 表示完全覆盖闭区间 [l, r] 所需要的最少区间数。
然而，直接定义二维状态 dp[l][r] 可能因 l 和 r 的范围过大（最大 10000）而导致空间和时间开销巨大。我们需要优化。

优化思路：

注意到所有区间的端点（包括目标区间的端点）构成了离散的点。我们可以将这些端点去重并排序，得到一个升序数组 points。这样，任何区间的起点和终点都可以映射为该数组中的索引。假设离散化后得到 M 个点（M ≤ 2*m + 2，最多约 2002），那么我们可以将状态定义为 dp[i][j]，表示覆盖从第 i 个点到第 j 个点所对应的连续区间所需要的最少区间数。
转移时，考虑用一个区间来覆盖 [points[i], points[j]] 的最左端部分，然后递归处理剩下的部分。因为区间不能重叠，所以被选中的区间必须恰好从 i 开始，然后结束于某个点 k（i < k ≤ j），并且这个区间必须是题目给定的 intervals 中的一个。之后，我们需要覆盖从 k 到 j 的部分。因此，状态转移方程为：
- 如果存在一个给定区间 [points[i], points[k]]（即离散化后端点对应 i 和 k），那么 dp[i][j] = 1 + dp[k][j]。
- 我们需要遍历所有可能的 k，取最小值。
最终答案是 dp[startIndex][endIndex]，其中 startIndex 和 endIndex 分别是 targetStart 和 targetEnd 在离散化数组中的索引。

边界条件：

如果 i == j，表示区间长度为 0（单个点），那么不需要任何区间就能覆盖（因为点自身被覆盖是题目要求，但覆盖一个点至少需要一个区间包含它。但我们的定义是覆盖闭区间，长度为0的区间实际上是一个点，仍需一个区间包含它。为避免混淆，我们约定：当 i==j 时，dp[i][j] = 0 当且仅当这个点本身就是目标的一部分，但因为我们从大于0长度开始，所以初始化时我们将 dp[i][j] 设为无穷大，除非有区间恰好覆盖 [points[i], points[j]]）。
我们初始化 dp[i][j] = INF（一个很大的数，表示不可行）。
然后，我们首先用所有单个区间来初始化对应的 dp 值：对于每个给定区间 [a, b]，找到其在离散化数组中的索引 i, j，则 dp[i][j] = 1（因为只需这一个区间就能覆盖它自身）。
之后，我们按照区间长度（按离散化后的索引差）从小到大进行动态规划。

3. 详细解题步骤

步骤1：预处理与离散化

收集所有区间的起点和终点，以及目标区间的起点和终点，放入一个列表。
对这个列表去重并排序，得到有序数组 points。
建立从坐标值到索引的映射 coord2idx，便于快速查找。

步骤2：初始化 DP 表

令 M = len(points)。
创建二维数组 dp，大小为 M x M，初始值设为 INF（例如 float('inf') 或一个大于最大区间数的大数，比如 m+1）。
遍历每个给定区间 [a, b]：
- 如果 a > b，跳过无效区间（但题目给定有效）。
- 在 points 中找到 a 和 b 对应的索引 i 和 j。
- 令 dp[i][j] = 1（因为只需这一个区间就能覆盖从 a 到 b 的范围）。
注意：如果目标区间 [targetStart, targetEnd] 本身就是一个给定的区间，那么答案可能就是 1。

步骤3：动态规划状态转移

我们按照区间长度（即 j - i 的大小）从小到大的顺序计算 dp[i][j]。
对于每一对 (i, j)，我们尝试找一个“分割点” k，使得存在一个给定区间覆盖 [points[i], points[k]]，然后加上覆盖 [points[k], points[j]] 的最小区间数。但更高效的方式是：枚举所有以 i 为左端点的给定区间，然后用它覆盖左边部分，再递归处理右边。
具体来说：
- 首先，dp[i][j] 可能已经由某个单个区间初始化好了（值为1），也可能尚未初始化（INF）。
- 然后，我们尝试使用一个区间覆盖最左边的一部分：对于所有给定区间 [a, b] 且 a 映射到索引 i，设 b 映射到索引 mid，那么如果 mid <= j，我们可以用这个区间覆盖 [i, mid]，然后还需要覆盖 [mid, j]。所以：
  - 如果 mid == j，则 dp[i][j] = min(dp[i][j], 1)（实际上就是单个区间覆盖整个，已经在初始化中处理了）。
  - 如果 mid < j，则 dp[i][j] = min(dp[i][j], 1 + dp[mid][j])。
- 注意：由于区间不能重叠，我们要求覆盖完 [i, mid] 后，下一个区间必须从 mid 开始（因为不能重叠，且我们需要连续覆盖，所以下一个区间的起点必须正好是 mid）。
另外，我们也可以考虑用更一般化的区间 DP 思想：dp[i][j] 可以分割为 dp[i][k] + dp[k][j] 吗？不行，因为分割点 k 可能不被任何区间覆盖，但我们的定义要求整个区间被完全覆盖。所以上面的“左区间 + 右边剩余部分”是正确的。

步骤4：获取答案

找到 targetStart 和 targetEnd 在 points 中的索引 i0 和 j0。
答案就是 dp[i0][j0]。如果其值大于等于 INF（或大于 m），则说明无法覆盖，返回 -1。

步骤5：复杂度分析

离散化：O(m log m)。
初始化：O(m)。
DP 计算：外层循环是区间长度 len 从 1 到 M-1，内层循环 i 从 0 到 M-1-len，j=i+len。对于每个状态 (i, j)，我们需要检查所有以 i 为左端点的给定区间。我们可以预处理一个列表 leftStart[i]，存储所有以点 i 为左端点的区间的右端点索引。这样，每个状态 (i, j) 的转移次数等于 leftStart[i] 中满足右端点索引 ≤ j 的个数。最坏情况下，每个左端点可能有 O(m) 个区间，所以总时间复杂度为 O(M² * m) 可能较高。但我们可以优化：在遍历状态 (i, j) 时，对于每个以 i 为左端点的区间，其右端点索引 mid 是固定的，我们只需更新 dp[i][j] 为 min(dp[i][j], 1 + dp[mid][j])，而这个更新只需要在 j ≥ mid 时才进行。我们可以反过来，在固定 i 和 mid 后，更新所有 j ≥ mid 的状态。这样，我们可以预先处理每个区间，然后动态更新。另一种方法是直接用记忆化搜索，避免无效状态。
由于 M 最大约 2002，m 最大 1000，O(M² * m) 可能达到 4e9，不可接受。因此，我们采用记忆化搜索 + 预处理右端点索引的方法，只计算必要的状态。

步骤6：实现细节（记忆化搜索优化）

用函数 dfs(i, j) 表示覆盖从点 i 到点 j 的最小区间数。
如果 i > j，返回 0（实际上不会发生，因为区间长度至少为0）。
如果 i == j，表示覆盖单个点，但单个点也需要一个区间包含它。然而，如果存在一个区间恰好覆盖 [points[i], points[i]]（即长度为0），那么 dp[i][i] 应为 1，否则为 INF。但题目中区间都是正长度的（start_i < end_i），所以不可能有长度为0的区间。因此，覆盖一个点至少需要一个区间包含这个点，但我们的状态是覆盖一个区间，所以当 i==j 时，实际上覆盖这个点需要至少一个区间，其左右端点包含这个点。但我们的定义是覆盖闭区间，所以 [i, i] 的覆盖，需要存在一个区间 [a, b] 使得 a ≤ points[i] ≤ b。但在我们的 dp 定义中，状态 [i, i] 实际上表示覆盖点 points[i] 到 points[i] 的闭区间，即长度为0。这通常需要0个区间吗？不，我们需要覆盖这个点，所以必须有一个区间包含它。为了简化，我们不在 DP 中单独处理点，而是从最小的正长度区间开始。因此，我们规定：只有当一个区间被完全覆盖时，状态才有定义。所以我们的初始状态是那些被单个给定区间覆盖的 [i, j]（i < j）。之后，在记忆化搜索中，我们只对 i < j 的状态进行计算。
记忆化搜索：
- 如果已经计算过 dp[i][j]，直接返回。
- 先查看是否有单个区间直接覆盖 [i, j]，有则 dp[i][j] = 1。
- 然后，遍历所有以 i 为左端点的给定区间，设其右端点索引为 mid，如果 mid ≤ j，则尝试用这个区间覆盖左边，然后递归计算 dfs(mid, j)，并更新 dp[i][j] = min(dp[i][j], 1 + dfs(mid, j))。
- 注意：可能存在多个区间以 i 为左端点，我们选最优。
最后，答案就是 dfs(i0, j0)，如果为 INF 则返回 -1。

4. 举例说明

使用题目示例：
intervals = [[1,3], [2,4], [3,5], [4,6]], targetStart = 1, targetEnd = 6

离散化：所有点为 {1,2,3,4,5,6}，排序后 points = [1,2,3,4,5,6]，索引 0~5。
初始化 dp：对于每个区间，设 dp[i][j]=1：
- [1,3] -> i=0, j=2, dp[0][2]=1
- [2,4] -> i=1, j=3, dp[1][3]=1
- [3,5] -> i=2, j=4, dp[2][4]=1
- [4,6] -> i=3, j=5, dp[3][5]=1
计算 dfs(0,5)（覆盖[1,6]）：
- 先看有无直接区间：没有 dp[0][5]=INF。
- 考虑以 i=0 为左端点的区间：[1,3] 对应 mid=2。
  - 然后计算 dfs(2,5)（覆盖[3,6]）。
    - dfs(2,5)：无直接区间。考虑以 i=2 为左端点的区间：[3,5] 对应 mid=4。
      - 然后计算 dfs(4,5)（覆盖[5,6]）。
        
        dfs(4,5)：无直接区间。考虑以 i=4 为左端点的区间：无。所以 dp[4][5]=INF，不可行。
    - 因此，从 [3,5] 这个区间尝试失败。
    - 再无其他以 2 为左的区间，所以 dp[2][5]=INF。
  - 所以 1+dfs(2,5)=1+INF=INF。
- 没有其他以 0 为左的区间，所以 dp[0][5]=INF，但这是错误的！因为我们知道答案是2，由 [1,3] 和 [4,6] 组成。
  问题出在哪里？当我们用 [1,3] 覆盖 [0,2] 后，我们需要覆盖 [2,5]（即[3,6]），但我们的递归调用是 dfs(2,5)，这意味着下一个区间必须从点 3 开始。然而，[4,6] 是从点 4 开始的，中间 [3,4] 这一段没有被覆盖。所以我们的递归定义要求区间严格首尾相接，没有间隙。但题目要求是覆盖整个目标区间，允许区间之间有间隙吗？不允许，因为覆盖要求并集覆盖目标区间，所以不能有间隙。因此，当我们用 [1,3] 覆盖了 [1,3] 后，[3,4] 这一段没有被覆盖，但目标区间 [1,6] 中的点 3 已经被覆盖了（因为闭区间，[1,3] 覆盖了点 3），但点 3 到点 4 之间的开区间 (3,4) 没有被覆盖，而目标区间 [1,6] 包括 (3,4) 中的所有点，所以我们必须覆盖它们。因此，我们不能让 [1,3] 和 [4,6] 之间有空隙。所以，实际上 [1,3] 和 [4,6] 并不能覆盖 [1,6]，因为点 3.5 没有被覆盖。但题目示例中说它们覆盖了 [1,6]，这是因为区间是整数点吗？题目中区间是闭区间，且端点都是整数，但覆盖的是连续区间，所以目标区间 [1,6] 包括所有实数 x 满足 1≤x≤6。如果只选择整数区间，那么必须覆盖所有实数点，但 [1,3] 和 [4,6] 之间 (3,4) 中的实数点没有被覆盖。所以题目实际上默认只考虑整数点？通常在这种区间覆盖问题中，我们默认区间覆盖整数点，即覆盖所有整数 x 满足 start ≤ x ≤ end。那么对于整数点，[1,3] 覆盖 {1,2,3}，[4,6] 覆盖 {4,5,6}，所以 {1,2,3,4,5,6} 都被覆盖了，中间没有整数点遗漏。因此，我们需要明确：覆盖的是整数点。那么我们的离散化点就是所有整数端点，状态 [i,j] 表示覆盖从 points[i] 到 points[j] 的所有整数点。这样，区间 [1,3] 和 [4,6] 之间没有整数点，所以是可行的。在我们的状态定义中，[i,j] 表示覆盖闭区间 [points[i], points[j]] 中的所有整数点。那么，当我们用区间 [1,3] 覆盖了索引 0~2 后，接下来需要覆盖从 points[2] 的下一个整数点开始，即 points[2]+1 = 4，但 points[2] 是 3，下一个整数点是 4，对应索引 3。所以，我们的递归调用应该是 dfs(3,5) 而不是 dfs(2,5)。即，覆盖了 [points[i], points[mid]] 后，下一个区间应该从 points[mid]+1 开始。但由于我们离散化的点是所有端点，points[mid]+1 可能不是某个端点，因此我们需要调整。

修正：

我们定义状态 dp[i][j] 表示覆盖从 points[i] 到 points[j] 的所有整数点的最小区间数。
那么，当我们选择一个区间 [points[i], points[mid]] 后，下一个需要覆盖的起点应该是 points[mid] + 1。我们需要找到第一个离散化点 ≥ points[mid] + 1 的索引 k。然后递归计算 dp[k][j]。
如果 points[mid] + 1 > points[j]，则说明覆盖完了，递归部分为 0。
在离散化点数组中，我们可以用二分查找找到 k。

重新计算示例：

离散化点同前：points = [1,2,3,4,5,6]。
计算 dfs(0,5)：
- 考虑区间 [1,3] (i=0, mid=2)。points[mid]+1 = 4，在 points 中索引为 3。所以递归 dfs(3,5)。
  - dfs(3,5)：考虑区间 [4,6] (i=3, mid=5)。points[mid]+1=7 > points[5]=6，所以递归部分为0。所以 dfs(3,5) = 1。
- 因此 dfs(0,5) = min(INF, 1 + dfs(3,5)) = 2。
得到答案 2，正确。

5. 最终算法步骤

离散化所有区间的端点和目标端点，得到排序去重的数组 points，长度 M。
预处理：对于每个区间 [a,b]，找到 a 和 b 在 points 中的索引 i 和 j，将区间按左端点索引 i 分组，存储右端点索引 j。得到列表 leftStart[i]。
记忆化搜索函数 dfs(l, r)：
- 如果 l > r: 返回 0（因为不需要区间）。
- 如果 dp[l][r] 已计算，返回。
- 初始化 ans = INF。
- 对于每个在 leftStart[l] 中的右端点索引 mid：
  - 如果 points[mid] > points[r]，则跳过（因为区间超出范围）。
  - 计算 next_l：在 points 中二分查找第一个点 ≥ points[mid] + 1 的索引 k。如果 k > r，则 next_l = r+1（表示右边为空），否则 next_l = k。
  - 递归计算 right = dfs(next_l, r)。
  - 如果 right != INF，则更新 ans = min(ans, 1 + right)。
- 存储 dp[l][r] = ans，返回 ans。
找到 targetStart 和 targetEnd 的索引 l0, r0。
计算 res = dfs(l0, r0)。如果 res >= INF，返回 -1，否则返回 res。

时间复杂度：状态数 O(M²)，每个状态需要遍历所有以 l 为左端点的区间，每个区间二分查找 O(log M)，所以总复杂度 O(M² * m_log M)，在 M≈2000, m=1000 时约为 4e9，仍然较大。但实际中，每个左端点对应的区间数远小于 m，且很多状态不会计算到（因为只有 l ≤ r 且 l 和 r 是端点的状态才可能达到）。我们可以用递推优化：按照区间长度递增计算 dp[l][r]，并利用提前预处理好的“下一个左端点索引”来避免二分查找。但为了清晰，记忆化搜索是可行的，只要加上剪枝。

进一步优化：注意到目标区间是固定的，我们可以用贪心算法？但题目要求区间互不相交，且要最少数目，这类似于用最少的线段覆盖指定区间，且线段不重叠。这实际上是一个区间调度覆盖问题，可以转化为图论中的最短路问题：将每个区间视为一条从起点到终点的边，然后我们需要从 targetStart 到 targetEnd 的一条路径，且经过的边不重叠（但可以首尾相接，即前一条边的终点+1 ≤ 后一条边的起点？实际上，因为我们覆盖的是整数点，所以前一条边的终点和后一条边的起点之间可以有空隙吗？不能，因为要覆盖所有整数点，所以必须满足前一条边的终点+1 ≥ 后一条边的起点？不，前一条边的终点和后一条边的起点之间不能有空隙，但允许重叠吗？不允许，因为题目要求区间互不相交。所以，必须满足前一条边的终点 < 后一条边的起点。但为了覆盖所有整数点，必须满足前一条边的终点+1 = 后一条边的起点。因此，这变成了一条从 targetStart 到 targetEnd 的路径，每条边是一个区间，且相邻区间满足前一个的终点+1 = 后一个的起点。这样，我们可以用 BFS 求最短路。但区间数只有 1000，我们可以用动态规划：设 dp[x] 表示覆盖从 targetStart 到 x 的最少区间数，然后按照区间起点排序，进行转移。但这要求区间是整数点，且目标区间是连续的整数区间。这种方法是更优的，时间复杂度 O(m log m + m * n)，但 n 可能很大（10000）。由于区间数只有 1000，我们可以用离散化后 DP。

更简洁的 DP 方法（推荐）：

将所有区间按照起点排序。
我们只关心从 targetStart 到 targetEnd 的覆盖，所以定义 dp[i] 表示覆盖从 targetStart 到点 i 的最少区间数，其中 i 是离散化后的点。
初始化 dp[targetStart] = 0，其他为 INF。
按照区间起点升序处理每个区间 [a,b]：
- 如果 a > targetEnd 或者 b < targetStart，则忽略。
- 设覆盖起点 s = max(a, targetStart)，覆盖终点 t = min(b, targetEnd)。
- 我们需要用这个区间覆盖 [s, t]。那么，对于这个区间，我们可以从 dp[a-1] 转移过来（因为区间不能重叠，前一个区间的终点必须 < a，所以前一个区间的终点最多是 a-1）。但我们的状态是覆盖到某一点，所以更精确地，我们定义 dp[x] 表示覆盖 [targetStart, x] 的最少区间数，且 x 是被覆盖的最后一个点。那么，当我们使用区间 [a,b] 时，如果当前已经覆盖到 a-1（即 dp[a-1] 可行），那么我们可以扩展到 b，即 dp[b] = min(dp[b], dp[a-1] + 1)。但注意，我们要求区间互不相交，所以前一个区间的终点必须 < a，即我们已经覆盖到 a-1，那么加上区间 [a,b] 后，就覆盖到了 b。
因此，算法步骤：
1. 将目标区间和所有区间都视为整数点。
2. 离散化所有点，但这次我们需要包括 targetStart-1 和 targetEnd，因为状态转移需要 a-1。
3. 对区间按起点排序。
4. 初始化 dp 数组，大小为离散化点数，dp[idx(targetStart-1)] = 0（表示覆盖到 targetStart-1 需要 0 个区间，即还没开始覆盖）。
5. 遍历每个区间 [a,b]：
  - 如果 a > targetEnd 或 b < targetStart，跳过。
  - 计算 need = max(a, targetStart)，然后检查 dp[need-1] 是否可到达（即不是 INF）。如果可到达，则用这个区间可以覆盖到 min(b, targetEnd)。更新 dp[min(b, targetEnd)] = min(dp[min(b, targetEnd)], dp[need-1] + 1)。
6. 最终答案 dp[idx(targetEnd)]，如果为 INF 则 -1。

这个方法是一维 DP，时间复杂度 O(m log m)（排序） + O(m)（遍历区间），空间 O(N) 或 O(M)。

举例：
intervals = [[1,3],[2,4],[3,5],[4,6]], target=[1,6]
离散化点：包括 targetStart-1=0, 以及所有区间端点和 targetEnd，得到 points=[0,1,2,3,4,5,6]。
初始化 dp: dp[0]=0（对应点0），其他 INF。
按区间起点排序后处理：

区间[1,3]: a=1,b=3, need=max(1,1)=1, need-1=0, dp[0]=0 可达，所以更新 dp[3]=min(INF,0+1)=1。
区间[2,4]: a=2, need=2, need-1=1, dp[1]=INF 不可达，跳过。
区间[3,5]: a=3, need=3, need-1=2, dp[2]=INF 不可达，跳过。
区间[4,6]: a=4, need=4, need-1=3, dp[3]=1 可达，所以更新 dp[6]=min(INF,1+1)=2。
最终 dp[6]=2，对应点6，即 targetEnd，答案2。

这个方法更高效且易于实现。

6. 最终答案

采用一维 DP 方法，步骤如下：

将所有区间的起点、终点，以及 targetStart-1, targetStart, targetEnd 加入一个集合，去重排序得到数组 points，并建立值到索引的映射。
初始化 dp 数组，长度为 len(points)，所有值为 INF。设 startIdx 为 targetStart 在 points 中的索引，startPrevIdx 为 targetStart-1 的索引，endIdx 为 targetEnd 的索引。令 dp[startPrevIdx] = 0。
将 intervals 按起点从小到大排序。
对于每个区间 [a,b]：
- 如果 a > targetEnd 或 b < targetStart，跳过。
- 计算 need = max(a, targetStart)，在 points 中找到 need-1 的索引 prevIdx（因为 need-1 可能不在 points 中，但我们在离散化时已经包含了 targetStart-1，而 need-1 可能小于 targetStart-1，此时应该取 targetStart-1 对应的索引。实际上，当 a > targetStart 时，need-1 = a-1，但 a-1 可能不在离散化点中。我们需要保证 dp 状态是定义在离散化点上的，所以我们需要找到第一个 ≤ need-1 的点的索引。但更简单的做法是：我们只考虑从 targetStart-1 开始转移，因为覆盖必须从 targetStart 开始。所以，我们要求区间起点 a ≤ targetStart 吗？不，区间起点可以大于 targetStart，但这样 targetStart 到 a-1 这一段就没有被覆盖，所以不可行。因此，只有 a ≤ targetStart 的区间才能作为第一个区间。但我们的转移是基于 dp[a-1]，如果 a > targetStart，那么 a-1 ≥ targetStart，而 dp[a-1] 表示覆盖到 a-1 的状态，但我们需要从 targetStart 开始覆盖，所以 dp[a-1] 可能未定义。实际上，正确的条件是：我们需要保证区间覆盖 targetStart 到 b 的部分，且之前已经覆盖到 a-1。但 a-1 可能小于 targetStart，此时 dp[a-1] 应该是 0（即从 targetStart-1 开始）。所以，我们统一用 dp[max(a, targetStart)-1] 作为前驱状态。而 max(a, targetStart)-1 可能小于 targetStart-1，这时前驱状态应该是 dp[targetStart-1]。因此，我们设 prev = max(a, targetStart)-1，然后在离散化点中找到最后一个 ≤ prev 的点的索引，作为前驱索引。由于我们离散化了所有点，可以二分查找。
- 找到前驱索引 prevIdx 后，如果 dp[prevIdx] 是 INF，则跳过。
- 计算覆盖终点 t = min(b, targetEnd)，找到 t 在 points 中的索引 tIdx。
- 更新 dp[tIdx] = min(dp[tIdx], dp[prevIdx] + 1)。
最终，如果 dp[endIdx] 是 INF，返回 -1，否则返回 dp[endIdx]。

注意：此方法要求区间互不相交，且覆盖所有整数点。它本质上是最短路问题，每个区间是一条从 a-1 到 b 的边，权重为1，我们求从 targetStart-1 到 targetEnd 的最短路径。可以用 Dijkstra，但这里因为权重为1，可以用 BFS 或 DP。由于区间已排序，DP 是线性。

时间复杂度：排序 O(m log m)，离散化 O(m log m)，DP 过程 O(m log m)（因为每次二分查找）。空间 O(m)。

总结：本题是区间覆盖问题的变种，核心是选择不相交区间以完全覆盖目标区间。通过离散化坐标和一维 DP（或最短路）可以高效求解。重点在于状态定义为覆盖到某点的最小区间数，利用区间起点和终点进行转移。

区间动态规划例题：区间覆盖问题（最小选择不相交区间使得覆盖指定连续范围） 1. 题目描述你获得一个闭区间的集合 intervals ，其中每个区间形如 [start_i, end_i] （满足 0 <= start_i <= end_i <= n ）。同时，你被给定一个目标区间 [targetStart, targetEnd] 。你需要从 intervals 中选择一个子集，使得这些区间互不相交（即，任意两个被选中的区间都没有重叠，即使只在端点重叠也不允许），并且它们的并集能够完全覆盖目标区间 [targetStart, targetEnd] （即，目标区间内的每个点都必须被至少一个所选区间覆盖）。问：至少需要选择多少个区间才能满足条件？如果无法覆盖目标区间，则返回 -1。示例输入： intervals = [[1,3], [2,4], [3,5], [4,6]] , targetStart = 1 , targetEnd = 6 输出： 2 解释：我们可以选择区间 [ 1,3] 和 [ 4,6]。这两个区间互不相交，并且它们的并集覆盖了 [ 1,6]。注意，我们不能选择 [ 1,3] 和 [ 3,5 ]，因为它们在点 3 处重叠（题目要求不相交，即端点也不能重叠）。数据范围区间个数 m 最多为 1000。所有区间的端点和目标区间的端点都在 [ 0, n ] 范围内，n 最大为 10000。 2. 解题思路这是一个区间选择与覆盖问题，由于需要满足“所选区间互不相交”且“完全覆盖一个连续的目标区间”，我们可以将问题转化为在给定的区间集合中，寻找一条从目标起点到目标终点的、由不重叠区间“拼接”而成的路径。这很适合用区间动态规划来求解，其中状态通常定义为“覆盖某个连续区间的最小代价（这里是最小区间数）”。关键观察：因为要求所选区间互不相交，所以如果我们按照区间的起点（或终点）排序，可以更方便地判断它们是否可能相邻。为了用动态规划覆盖从 targetStart 到 targetEnd 的连续范围，我们可以定义状态 dp[l][r] 表示完全覆盖闭区间 [ l, r] 所需要的最少区间数。然而，直接定义二维状态 dp[l][r] 可能因 l 和 r 的范围过大（最大 10000）而导致空间和时间开销巨大。我们需要优化。优化思路：注意到所有区间的端点（包括目标区间的端点）构成了离散的点。我们可以将这些端点去重并排序，得到一个升序数组 points 。这样，任何区间的起点和终点都可以映射为该数组中的索引。假设离散化后得到 M 个点（M ≤ 2* m + 2，最多约 2002），那么我们可以将状态定义为 dp[i][j] ，表示覆盖从第 i 个点到第 j 个点所对应的连续区间所需要的最少区间数。转移时，考虑用一个区间来覆盖 [points[i], points[j]] 的最左端部分，然后递归处理剩下的部分。因为区间不能重叠，所以被选中的区间必须恰好从 i 开始，然后结束于某个点 k（i < k ≤ j），并且这个区间必须是题目给定的 intervals 中的一个。之后，我们需要覆盖从 k 到 j 的部分。因此，状态转移方程为：如果存在一个给定区间 [points[i], points[k]] （即离散化后端点对应 i 和 k），那么 dp[i][j] = 1 + dp[k][j] 。我们需要遍历所有可能的 k，取最小值。最终答案是 dp[startIndex][endIndex] ，其中 startIndex 和 endIndex 分别是 targetStart 和 targetEnd 在离散化数组中的索引。边界条件：如果 i == j ，表示区间长度为 0（单个点），那么不需要任何区间就能覆盖（因为点自身被覆盖是题目要求，但覆盖一个点至少需要一个区间包含它。但我们的定义是覆盖闭区间，长度为0的区间实际上是一个点，仍需一个区间包含它。为避免混淆，我们约定：当 i==j 时， dp[i][j] = 0 当且仅当这个点本身就是目标的一部分，但因为我们从大于0长度开始，所以初始化时我们将 dp[i][j] 设为无穷大，除非有区间恰好覆盖 [points[i], points[j]] ）。我们初始化 dp[i][j] = INF （一个很大的数，表示不可行）。然后，我们首先用所有单个区间来初始化对应的 dp 值：对于每个给定区间 [a, b] ，找到其在离散化数组中的索引 i , j ，则 dp[i][j] = 1 （因为只需这一个区间就能覆盖它自身）。之后，我们按照区间长度（按离散化后的索引差）从小到大进行动态规划。 3. 详细解题步骤步骤1：预处理与离散化收集所有区间的起点和终点，以及目标区间的起点和终点，放入一个列表。对这个列表去重并排序，得到有序数组 points 。建立从坐标值到索引的映射 coord2idx ，便于快速查找。步骤2：初始化 DP 表令 M = len(points) 。创建二维数组 dp ，大小为 M x M ，初始值设为 INF （例如 float('inf') 或一个大于最大区间数的大数，比如 m+1）。遍历每个给定区间 [a, b] ：如果 a > b ，跳过无效区间（但题目给定有效）。在 points 中找到 a 和 b 对应的索引 i 和 j 。令 dp[i][j] = 1 （因为只需这一个区间就能覆盖从 a 到 b 的范围）。注意：如果目标区间 [targetStart, targetEnd] 本身就是一个给定的区间，那么答案可能就是 1。步骤3：动态规划状态转移我们按照区间长度（即 j - i 的大小）从小到大的顺序计算 dp[i][j] 。对于每一对 (i, j) ，我们尝试找一个“分割点” k，使得存在一个给定区间覆盖 [points[i], points[k]] ，然后加上覆盖 [points[k], points[j]] 的最小区间数。但更高效的方式是：枚举所有以 i 为左端点的给定区间，然后用它覆盖左边部分，再递归处理右边。具体来说：首先， dp[i][j] 可能已经由某个单个区间初始化好了（值为1），也可能尚未初始化（INF）。然后，我们尝试使用一个区间覆盖最左边的一部分：对于所有给定区间 [a, b] 且 a 映射到索引 i，设 b 映射到索引 mid，那么如果 mid <= j ，我们可以用这个区间覆盖 [i, mid] ，然后还需要覆盖 [mid, j] 。所以：如果 mid == j ，则 dp[i][j] = min(dp[i][j], 1) （实际上就是单个区间覆盖整个，已经在初始化中处理了）。如果 mid < j ，则 dp[i][j] = min(dp[i][j], 1 + dp[mid][j]) 。注意：由于区间不能重叠，我们要求覆盖完 [i, mid] 后，下一个区间必须从 mid 开始（因为不能重叠，且我们需要连续覆盖，所以下一个区间的起点必须正好是 mid）。另外，我们也可以考虑用更一般化的区间 DP 思想： dp[i][j] 可以分割为 dp[i][k] + dp[k][j] 吗？不行，因为分割点 k 可能不被任何区间覆盖，但我们的定义要求整个区间被完全覆盖。所以上面的“左区间 + 右边剩余部分”是正确的。步骤4：获取答案找到 targetStart 和 targetEnd 在 points 中的索引 i0 和 j0 。答案就是 dp[i0][j0] 。如果其值大于等于 INF（或大于 m），则说明无法覆盖，返回 -1。步骤5：复杂度分析离散化：O(m log m)。初始化：O(m)。 DP 计算：外层循环是区间长度 len 从 1 到 M-1，内层循环 i 从 0 到 M-1-len，j=i+len。对于每个状态 (i, j)，我们需要检查所有以 i 为左端点的给定区间。我们可以预处理一个列表 leftStart[i] ，存储所有以点 i 为左端点的区间的右端点索引。这样，每个状态 (i, j) 的转移次数等于 leftStart[i] 中满足右端点索引 ≤ j 的个数。最坏情况下，每个左端点可能有 O(m) 个区间，所以总时间复杂度为 O(M² * m) 可能较高。但我们可以优化：在遍历状态 (i, j) 时，对于每个以 i 为左端点的区间，其右端点索引 mid 是固定的，我们只需更新 dp[i][j] 为 min(dp[i][j], 1 + dp[mid][j]) ，而这个更新只需要在 j ≥ mid 时才进行。我们可以反过来，在固定 i 和 mid 后，更新所有 j ≥ mid 的状态。这样，我们可以预先处理每个区间，然后动态更新。另一种方法是直接用记忆化搜索，避免无效状态。由于 M 最大约 2002，m 最大 1000，O(M² * m) 可能达到 4e9，不可接受。因此，我们采用记忆化搜索 + 预处理右端点索引的方法，只计算必要的状态。步骤6：实现细节（记忆化搜索优化）用函数 dfs(i, j) 表示覆盖从点 i 到点 j 的最小区间数。如果 i > j ，返回 0（实际上不会发生，因为区间长度至少为0）。如果 i == j ，表示覆盖单个点，但单个点也需要一个区间包含它。然而，如果存在一个区间恰好覆盖 [points[i], points[i]] （即长度为0），那么 dp[i][i] 应为 1，否则为 INF。但题目中区间都是正长度的（ start_i < end_i ），所以不可能有长度为0的区间。因此，覆盖一个点至少需要一个区间包含这个点，但我们的状态是覆盖一个区间，所以当 i==j 时，实际上覆盖这个点需要至少一个区间，其左右端点包含这个点。但我们的定义是覆盖闭区间，所以 [i, i] 的覆盖，需要存在一个区间 [a, b] 使得 a ≤ points[ i] ≤ b。但在我们的 dp 定义中，状态 [i, i] 实际上表示覆盖点 points[ i] 到 points[ i] 的闭区间，即长度为0。这通常需要0个区间吗？不，我们需要覆盖这个点，所以必须有一个区间包含它。为了简化，我们不在 DP 中单独处理点，而是从最小的正长度区间开始。因此，我们规定：只有当一个区间被完全覆盖时，状态才有定义。所以我们的初始状态是那些被单个给定区间覆盖的 [i, j] （i < j）。之后，在记忆化搜索中，我们只对 i < j 的状态进行计算。记忆化搜索：如果已经计算过 dp[i][j] ，直接返回。先查看是否有单个区间直接覆盖 [i, j] ，有则 dp[i][j] = 1 。然后，遍历所有以 i 为左端点的给定区间，设其右端点索引为 mid，如果 mid ≤ j，则尝试用这个区间覆盖左边，然后递归计算 dfs(mid, j) ，并更新 dp[i][j] = min(dp[i][j], 1 + dfs(mid, j)) 。注意：可能存在多个区间以 i 为左端点，我们选最优。最后，答案就是 dfs(i0, j0) ，如果为 INF 则返回 -1。 4. 举例说明使用题目示例： intervals = [[1,3], [2,4], [3,5], [4,6]] , targetStart = 1 , targetEnd = 6 离散化：所有点为 {1,2,3,4,5,6}，排序后 points = [1,2,3,4,5,6] ，索引 0~5。初始化 dp ：对于每个区间，设 dp[i][j]=1 ： [ 1,3] -> i=0, j=2, dp[ 0][ 2 ]=1 [ 2,4] -> i=1, j=3, dp[ 1][ 3 ]=1 [ 3,5] -> i=2, j=4, dp[ 2][ 4 ]=1 [ 4,6] -> i=3, j=5, dp[ 3][ 5 ]=1 计算 dfs(0,5) （覆盖[ 1,6 ]）：先看有无直接区间：没有 dp[ 0][ 5 ]=INF。考虑以 i=0 为左端点的区间：[ 1,3 ] 对应 mid=2。然后计算 dfs(2,5)（覆盖[ 3,6 ]）。 dfs(2,5)：无直接区间。考虑以 i=2 为左端点的区间：[ 3,5 ] 对应 mid=4。然后计算 dfs(4,5)（覆盖[ 5,6 ]）。 dfs(4,5)：无直接区间。考虑以 i=4 为左端点的区间：无。所以 dp[ 4][ 5 ]=INF，不可行。因此，从 [ 3,5 ] 这个区间尝试失败。再无其他以 2 为左的区间，所以 dp[ 2][ 5 ]=INF。所以 1+dfs(2,5)=1+INF=INF。没有其他以 0 为左的区间，所以 dp[ 0][ 5]=INF，但这是错误的！因为我们知道答案是2，由 [ 1,3] 和 [ 4,6 ] 组成。问题出在哪里？当我们用 [ 1,3] 覆盖 [ 0,2] 后，我们需要覆盖 [ 2,5]（即[ 3,6]），但我们的递归调用是 dfs(2,5)，这意味着下一个区间必须从点 3 开始。然而，[ 4,6] 是从点 4 开始的，中间 [ 3,4] 这一段没有被覆盖。所以我们的递归定义要求区间严格首尾相接，没有间隙。但题目要求是覆盖整个目标区间，允许区间之间有间隙吗？不允许，因为覆盖要求并集覆盖目标区间，所以不能有间隙。因此，当我们用 [ 1,3] 覆盖了 [ 1,3] 后，[ 3,4] 这一段没有被覆盖，但目标区间 [ 1,6] 中的点 3 已经被覆盖了（因为闭区间，[ 1,3] 覆盖了点 3），但点 3 到点 4 之间的开区间 (3,4) 没有被覆盖，而目标区间 [ 1,6] 包括 (3,4) 中的所有点，所以我们必须覆盖它们。因此，我们不能让 [ 1,3] 和 [ 4,6] 之间有空隙。所以，实际上 [ 1,3] 和 [ 4,6] 并不能覆盖 [ 1,6]，因为点 3.5 没有被覆盖。但题目示例中说它们覆盖了 [ 1,6]，这是因为区间是整数点吗？题目中区间是闭区间，且端点都是整数，但覆盖的是连续区间，所以目标区间 [ 1,6] 包括所有实数 x 满足 1≤x≤6。如果只选择整数区间，那么必须覆盖所有实数点，但 [ 1,3] 和 [ 4,6] 之间 (3,4) 中的实数点没有被覆盖。所以题目实际上默认只考虑整数点？通常在这种区间覆盖问题中，我们默认区间覆盖整数点，即覆盖所有整数 x 满足 start ≤ x ≤ end。那么对于整数点，[ 1,3] 覆盖 {1,2,3}，[ 4,6] 覆盖 {4,5,6}，所以 {1,2,3,4,5,6} 都被覆盖了，中间没有整数点遗漏。因此，我们需要明确：覆盖的是整数点。那么我们的离散化点就是所有整数端点，状态 [ i,j] 表示覆盖从 points[ i] 到 points[ j] 的所有整数点。这样，区间 [ 1,3] 和 [ 4,6] 之间没有整数点，所以是可行的。在我们的状态定义中，[ i,j] 表示覆盖闭区间 [ points[ i], points[ j]] 中的所有整数点。那么，当我们用区间 [ 1,3] 覆盖了索引 0~2 后，接下来需要覆盖从 points[ 2] 的下一个整数点开始，即 points[ 2]+1 = 4，但 points[ 2] 是 3，下一个整数点是 4，对应索引 3。所以，我们的递归调用应该是 dfs(3,5) 而不是 dfs(2,5)。即，覆盖了 [ points[ i], points[ mid]] 后，下一个区间应该从 points[ mid]+1 开始。但由于我们离散化的点是所有端点，points[ mid ]+1 可能不是某个端点，因此我们需要调整。修正：我们定义状态 dp[i][j] 表示覆盖从 points[ i] 到 points[ j] 的所有整数点的最小区间数。那么，当我们选择一个区间 [points[i], points[mid]] 后，下一个需要覆盖的起点应该是 points[mid] + 1 。我们需要找到第一个离散化点 ≥ points[mid] + 1 的索引 k。然后递归计算 dp[k][j] 。如果 points[mid] + 1 > points[j] ，则说明覆盖完了，递归部分为 0。在离散化点数组中，我们可以用二分查找找到 k。重新计算示例：离散化点同前： points = [1,2,3,4,5,6] 。计算 dfs(0,5) ：考虑区间 [ 1,3] (i=0, mid=2)。points[ mid]+1 = 4，在 points 中索引为 3。所以递归 dfs(3,5) 。 dfs(3,5) ：考虑区间 [ 4,6] (i=3, mid=5)。points[ mid]+1=7 > points[ 5]=6，所以递归部分为0。所以 dfs(3,5) = 1 。因此 dfs(0,5) = min(INF, 1 + dfs(3,5)) = 2 。得到答案 2，正确。 5. 最终算法步骤离散化所有区间的端点和目标端点，得到排序去重的数组 points ，长度 M。预处理：对于每个区间 [a,b] ，找到 a 和 b 在 points 中的索引 i 和 j，将区间按左端点索引 i 分组，存储右端点索引 j。得到列表 leftStart[i] 。记忆化搜索函数 dfs(l, r) ：如果 l > r: 返回 0（因为不需要区间）。如果 dp[l][r] 已计算，返回。初始化 ans = INF 。对于每个在 leftStart[l] 中的右端点索引 mid：如果 points[mid] > points[r] ，则跳过（因为区间超出范围）。计算 next_ l：在 points 中二分查找第一个点 ≥ points[mid] + 1 的索引 k。如果 k > r，则 next_ l = r+1（表示右边为空），否则 next_ l = k。递归计算 right = dfs(next_ l, r)。如果 right != INF，则更新 ans = min(ans, 1 + right)。存储 dp[l][r] = ans ，返回 ans。找到 targetStart 和 targetEnd 的索引 l0, r0。计算 res = dfs(l0, r0)。如果 res >= INF，返回 -1，否则返回 res。时间复杂度：状态数 O(M²)，每个状态需要遍历所有以 l 为左端点的区间，每个区间二分查找 O(log M)，所以总复杂度 O(M² * m_ log M)，在 M≈2000, m=1000 时约为 4e9，仍然较大。但实际中，每个左端点对应的区间数远小于 m，且很多状态不会计算到（因为只有 l ≤ r 且 l 和 r 是端点的状态才可能达到）。我们可以用递推优化：按照区间长度递增计算 dp[ l][ r ]，并利用提前预处理好的“下一个左端点索引”来避免二分查找。但为了清晰，记忆化搜索是可行的，只要加上剪枝。进一步优化：注意到目标区间是固定的，我们可以用贪心算法？但题目要求区间互不相交，且要最少数目，这类似于用最少的线段覆盖指定区间，且线段不重叠。这实际上是一个区间调度覆盖问题，可以转化为图论中的最短路问题：将每个区间视为一条从起点到终点的边，然后我们需要从 targetStart 到 targetEnd 的一条路径，且经过的边不重叠（但可以首尾相接，即前一条边的终点+1 ≤ 后一条边的起点？实际上，因为我们覆盖的是整数点，所以前一条边的终点和后一条边的起点之间可以有空隙吗？不能，因为要覆盖所有整数点，所以必须满足前一条边的终点+1 ≥ 后一条边的起点？不，前一条边的终点和后一条边的起点之间不能有空隙，但允许重叠吗？不允许，因为题目要求区间互不相交。所以，必须满足前一条边的终点 < 后一条边的起点。但为了覆盖所有整数点，必须满足前一条边的终点+1 = 后一条边的起点。因此，这变成了一条从 targetStart 到 targetEnd 的路径，每条边是一个区间，且相邻区间满足前一个的终点+1 = 后一个的起点。这样，我们可以用 BFS 求最短路。但区间数只有 1000，我们可以用动态规划：设 dp[ x] 表示覆盖从 targetStart 到 x 的最少区间数，然后按照区间起点排序，进行转移。但这要求区间是整数点，且目标区间是连续的整数区间。这种方法是更优的，时间复杂度 O(m log m + m * n)，但 n 可能很大（10000）。由于区间数只有 1000，我们可以用离散化后 DP。更简洁的 DP 方法（推荐）：将所有区间按照起点排序。我们只关心从 targetStart 到 targetEnd 的覆盖，所以定义 dp[ i ] 表示覆盖从 targetStart 到点 i 的最少区间数，其中 i 是离散化后的点。初始化 dp[ targetStart ] = 0，其他为 INF。按照区间起点升序处理每个区间 [ a,b ]：如果 a > targetEnd 或者 b < targetStart，则忽略。设覆盖起点 s = max(a, targetStart)，覆盖终点 t = min(b, targetEnd)。我们需要用这个区间覆盖 [ s, t]。那么，对于这个区间，我们可以从 dp[ a-1] 转移过来（因为区间不能重叠，前一个区间的终点必须 < a，所以前一个区间的终点最多是 a-1）。但我们的状态是覆盖到某一点，所以更精确地，我们定义 dp[ x] 表示覆盖 [ targetStart, x] 的最少区间数，且 x 是被覆盖的最后一个点。那么，当我们使用区间 [ a,b] 时，如果当前已经覆盖到 a-1（即 dp[ a-1] 可行），那么我们可以扩展到 b，即 dp[ b] = min(dp[ b], dp[ a-1] + 1)。但注意，我们要求区间互不相交，所以前一个区间的终点必须 < a，即我们已经覆盖到 a-1，那么加上区间 [ a,b ] 后，就覆盖到了 b。因此，算法步骤：将目标区间和所有区间都视为整数点。离散化所有点，但这次我们需要包括 targetStart-1 和 targetEnd，因为状态转移需要 a-1。对区间按起点排序。初始化 dp 数组，大小为离散化点数，dp[ idx(targetStart-1) ] = 0（表示覆盖到 targetStart-1 需要 0 个区间，即还没开始覆盖）。遍历每个区间 [ a,b ]：如果 a > targetEnd 或 b < targetStart，跳过。计算 need = max(a, targetStart)，然后检查 dp[ need-1] 是否可到达（即不是 INF）。如果可到达，则用这个区间可以覆盖到 min(b, targetEnd)。更新 dp[ min(b, targetEnd)] = min(dp[ min(b, targetEnd)], dp[ need-1 ] + 1)。最终答案 dp[ idx(targetEnd) ]，如果为 INF 则 -1。这个方法是一维 DP ，时间复杂度 O(m log m)（排序） + O(m)（遍历区间），空间 O(N) 或 O(M)。举例： intervals = [ [ 1,3],[ 2,4],[ 3,5],[ 4,6]], target=[ 1,6 ] 离散化点：包括 targetStart-1=0, 以及所有区间端点和 targetEnd，得到 points=[ 0,1,2,3,4,5,6 ]。初始化 dp: dp[ 0 ]=0（对应点0），其他 INF。按区间起点排序后处理：区间[ 1,3]: a=1,b=3, need=max(1,1)=1, need-1=0, dp[ 0]=0 可达，所以更新 dp[ 3 ]=min(INF,0+1)=1。区间[ 2,4]: a=2, need=2, need-1=1, dp[ 1 ]=INF 不可达，跳过。区间[ 3,5]: a=3, need=3, need-1=2, dp[ 2 ]=INF 不可达，跳过。区间[ 4,6]: a=4, need=4, need-1=3, dp[ 3]=1 可达，所以更新 dp[ 6 ]=min(INF,1+1)=2。最终 dp[ 6 ]=2，对应点6，即 targetEnd，答案2。这个方法更高效且易于实现。 6. 最终答案采用一维 DP 方法，步骤如下：将所有区间的起点、终点，以及 targetStart-1, targetStart, targetEnd 加入一个集合，去重排序得到数组 points ，并建立值到索引的映射。初始化 dp 数组，长度为 len(points)，所有值为 INF。设 startIdx 为 targetStart 在 points 中的索引， startPrevIdx 为 targetStart-1 的索引， endIdx 为 targetEnd 的索引。令 dp[startPrevIdx] = 0 。将 intervals 按起点从小到大排序。对于每个区间 [ a,b ]：如果 a > targetEnd 或 b < targetStart，跳过。计算 need = max(a, targetStart)，在 points 中找到 need-1 的索引 prevIdx （因为 need-1 可能不在 points 中，但我们在离散化时已经包含了 targetStart-1，而 need-1 可能小于 targetStart-1，此时应该取 targetStart-1 对应的索引。实际上，当 a > targetStart 时，need-1 = a-1，但 a-1 可能不在离散化点中。我们需要保证 dp 状态是定义在离散化点上的，所以我们需要找到第一个 ≤ need-1 的点的索引。但更简单的做法是：我们只考虑从 targetStart-1 开始转移，因为覆盖必须从 targetStart 开始。所以，我们要求区间起点 a ≤ targetStart 吗？不，区间起点可以大于 targetStart，但这样 targetStart 到 a-1 这一段就没有被覆盖，所以不可行。因此，只有 a ≤ targetStart 的区间才能作为第一个区间。但我们的转移是基于 dp[ a-1]，如果 a > targetStart，那么 a-1 ≥ targetStart，而 dp[ a-1] 表示覆盖到 a-1 的状态，但我们需要从 targetStart 开始覆盖，所以 dp[ a-1] 可能未定义。实际上，正确的条件是：我们需要保证区间覆盖 targetStart 到 b 的部分，且之前已经覆盖到 a-1。但 a-1 可能小于 targetStart，此时 dp[ a-1] 应该是 0（即从 targetStart-1 开始）。所以，我们统一用 dp[ max(a, targetStart)-1] 作为前驱状态。而 max(a, targetStart)-1 可能小于 targetStart-1，这时前驱状态应该是 dp[ targetStart-1 ]。因此，我们设 prev = max(a, targetStart)-1，然后在离散化点中找到最后一个 ≤ prev 的点的索引，作为前驱索引。由于我们离散化了所有点，可以二分查找。找到前驱索引 prevIdx 后，如果 dp[prevIdx] 是 INF，则跳过。计算覆盖终点 t = min(b, targetEnd)，找到 t 在 points 中的索引 tIdx 。更新 dp[ tIdx] = min(dp[ tIdx], dp[ prevIdx ] + 1)。最终，如果 dp[endIdx] 是 INF，返回 -1，否则返回 dp[endIdx] 。注意：此方法要求区间互不相交，且覆盖所有整数点。它本质上是最短路问题，每个区间是一条从 a-1 到 b 的边，权重为1，我们求从 targetStart-1 到 targetEnd 的最短路径。可以用 Dijkstra，但这里因为权重为1，可以用 BFS 或 DP。由于区间已排序，DP 是线性。时间复杂度：排序 O(m log m)，离散化 O(m log m)，DP 过程 O(m log m)（因为每次二分查找）。空间 O(m)。总结：本题是区间覆盖问题的变种，核心是选择不相交区间以完全覆盖目标区间。通过离散化坐标和一维 DP（或最短路）可以高效求解。重点在于状态定义为覆盖到某点的最小区间数，利用区间起点和终点进行转移。