区间覆盖贪心模型：从经典问题到跳跃游戏II的解法转换

在贪心算法里，区间覆盖是我最常拿来跟人“安利”的一类问题。它的贪心策略看起来非常直观——每一步都选覆盖到最远处的区间，可真正动手写代码时，很多人会栽在“什么时候计数、什么时候更新边界”这些细节上。今天这篇想聊的，是区间覆盖系列里的附加例题2：跳跃游戏II。这个题目很多同学第一次看到是在动态规划章节里，但如果换成区间覆盖的视角去理解，会发现它本质上就是一个“用最少的区间覆盖到终点”的贪心模型，而且可以做到一趟扫描、O(1)空间。这篇内容适合正在准备算法面试、刷LeetCode或打ACM选拔赛的朋友，也适合那些已经刷过跳跃游戏II、但始终觉得解法有点“玄”的同学。

1. 区间覆盖问题的本质与贪心依据

1.1 一个经典场景：洒水装置与覆盖区间

先从一个特别接地气的场景说起。假设有一段长度为 L 的马路需要洒水，路边有一些洒水装置，每个装置有一个覆盖范围参数。由于装置位置固定、喷洒半径也固定，每个装置实际上只能在马路上覆盖一个连续的子区间。现在的问题是：最少打开几个装置，就能让整段马路都被覆盖到？

把马路拉直成一条数轴，问题就变成了“给定目标区间 [L, R] 和若干个候选子区间，选出最少数量的子区间，使它们的并集完整覆盖 [L, R]”。这就是区间覆盖的经典模型。类似的场景还有：给一排教室安排无线AP、在一条线路上选址设置快递柜、在楼宇里安装消防喷淋头，本质上都逃不开这个模型。

这个模型之所以适合用贪心算法来解决，是因为它的结构非常规则：所有区间都在一维数轴上，区间之间存在天然的左右顺序。一旦把区间按左端点排好序，覆盖的过程就可以看作“当前点在一个方向上持续推进”，贪心决策的空间非常清晰。

1.2 贪心策略与正确性证明思路

区间覆盖的贪心策略一句话可以概括：在“所有能接上当前覆盖点的区间”里，选择右端点最远的那个。注意两个关键词：第一个是“能接上”，也就是区间的左端点不能大于当前已经覆盖到的位置；第二个是“右端点最远”，也就是在当前可选集合里，让覆盖范围尽量向前延伸。

为什么这个策略是对的？这里给出一个不依赖背模板的理解方式。假设当前覆盖点已经到了 pos，最优解接下来选择的是区间 A，而贪心算法选择的是区间 G。由于 G 是所有左端点不超过 pos 的区间中右端点最远的，所以 G 的右端点一定大于等于 A 的右端点。把最优解中的 A 替换成 G，后面的所有区间仍然可以正常接上，而且覆盖范围只会更大、不会更小。这意味着“使用 G 的最优解”是存在的。逐次替换下去，贪心选择的每一个区间都能出现在某个最优解中，于是贪心结果就是最优解。

这里要特别提醒一句：很多人背下这个结论后，容易忽略“能接上”这个前提。如果某个区间右端点再远，但它左端点已经在当前覆盖点右侧，中间出现了断档，那么它就不能被选择。这也是区间的排序方向为什么必须是左端点升序、而不是右端点升序的原因。

2. 例题铺垫：经典最小区间覆盖的实现细节

2.1 问题建模与排序方向

先看一道最经典的例题作为热身。给定目标区间 [L, R]（L、R 都是整数），再给 n 个区间，第 i 个区间的左右端点是 a[i] 和 b[i]。问能否从这些区间中选出若干个，完整覆盖 [L, R]；如果能，最少选几个。

拿到题目后第一步不是写代码，而是想清楚数据结构和排序规则。因为要在“左端点不超过当前覆盖点的所有区间”里找右端点最大者，一个自然的做法就是把所有区间按左端点从小到大排序。排序之后，扫描的过程就是不断把新满足条件的区间纳入“当前可选集合”。

这里有一个工程的思维小技巧：不需要真的维护一个独立的“可选集合”，只要维护一个变量 far，表示在当前覆盖点 pos 的前提下，所有左端点不超过 pos 的区间中，右端点最大能延伸到哪里。每扫过一个左端点不超过 pos 的区间，就用它的右端点去更新 far，扫描的同时完成选择，不需要额外数据结构。

2.2 扫描过程中的两个关键变量

写代码之前，先明确三个变量的含义：

• current：当前已经覆盖到的右端点。
• far：在 current 之下，扫描一轮后能延伸到的最大右端点。
• cnt：已经使用的区间数量。

每一轮扫描的流程是：遍历尚未处理的区间，凡是左端点小于等于 current 的区间，都用其右端点尝试更新 far。遍历完这一轮之后，会得到两种情况。第一种是 far 仍然等于 current，说明所有能接上的区间都已经用过了，但没有任何区间能把覆盖点再往前推，这时就是无法覆盖，直接终止。第二种是 far 大于 current，说明这一轮确实推进了覆盖点，那么 cnt 加一，把 current 更新为 far，进入下一轮继续扫描。

这个过程有一个很多人第一次写都会犯迷糊的点：扫描时只更新 far，不立刻给 cnt 加一。因为这一轮里的多个区间只是“候选”，真正被选中作为覆盖点延伸依据的，实际上只有那个让 far 取到最大值的区间，但你不必知道它具体是哪一个。一轮扫描对应一次区间选择，所以 cnt 在每轮扫描结束后统一增加。

2.3 带注释的参考实现

用 C++ 写一遍完整的实现，并配一组样例验证。

#include <bits/stdc++.h> using namespace std; struct Range { int l, r; bool operator<(const Range& o) const { return l < o.l; // 按左端点升序排序 } }; int main() { int L, R; cin >> L >> R; int n; cin >> n; vector<Range> a(n); for (int i = 0; i < n; i++) { cin >> a[i].l >> a[i].r; } sort(a.begin(), a.end()); int current = L; // 当前覆盖点 int idx = 0; int cnt = 0; bool ok = false; while (current < R) { int far = current; // 本轮能够延伸的最远位置 while (idx < n && a[idx].l <= current) { far = max(far, a[idx].r); idx++; } if (far == current) { // 没有区间能继续延伸，说明无法覆盖 ok = false; break; } cnt++; current = far; ok = true; } if (ok && current >= R) { cout << cnt << endl; } else { cout << "无法覆盖" << endl; } return 0; }

输入样例：

1 10 4 1 3 2 5 4 8 6 10

程序运行过程：

1. current = 1，扫描左端点不超过 1 的区间，只有 [1,3]，far 从 1 变成 3。far != current，cnt=1，current=3。
2. current = 3，扫描左端点不超过 3 的区间，有 [2,5]，far 变成 5。cnt=2，current=5。
3. current = 5，扫描左端点不超过 5 的区间，有 [4,8]，far 变成 8。cnt=3，current=8。
4. current = 8，扫描左端点不超过 8 的区间，有 [6,10]，far 变成 10。cnt=4，current=10。

最终 current >= R，输出 4。手动检查一下，[1,3]、[2,5]、[4,8]、[6,10] 四个区间确实覆盖了 [1,10]，但是不是最少后文会进一步分析。

3. 附加例题2：跳跃游戏II的区间覆盖视角

3.1 从“选区间”到“跳格子”的模型转化

热身题做完，进入今天的重头戏。在整理区间覆盖专题时，我加餐的第二个例题就是 LeetCode 45：跳跃游戏II。题目描述很简单：给定一个非负整数数组 nums，初始在下标 0 处。数组中的每个元素代表你在该位置能够跳跃的最大长度，也就是站在下标 i 时，可以跳到 [i, i + nums[i]] 范围内的任意整数下标。目标是以最少的跳跃次数到达最后一个下标。

乍一看，这和“区间覆盖”似乎完全是两套东西。但把下标看成数轴上的点，就会发现：站在某个位置 i 进行一次跳跃，能覆盖到的范围就是从 i 到 i + nums[i] 的连续区间。目标是从下标 0 出发，用尽可能少的跳跃区间，覆盖到最后一个位置 n-1。这不就是“最小区间覆盖”吗？

区别在于区间的来源。经典区间覆盖里所有候选区间是一开始就摆在那里的，选择时可以任意从中挑；跳跃游戏II中的区间则是一步一步“解锁”的——只有当你跳到了某个位置，你才知道从那个位置能往右覆盖多远。这种动态暴露候选区间的特点，也是它比经典题更容易让人懵的原因。

3.2 一次遍历完成贪心选择

跳跃游戏II的贪心核心可以这样描述：在当前这一跳可以到达的范围内，寻找“下一个可到达位置中右端点最远”的方案，也就是把所有候选落脚点的 i + nums[i] 都算出来，取最大值，作为下一跳能到达的右边界。

很多人第一次听到这个思路会质疑：这不是变成了“两步跳”的贪心吗？为什么还要考虑“下一个落脚点之后还能走多远”？这正是区间覆盖视角给出的答案：我们选的从来不是一个“点”，而是一个“区间”。站在当前范围内的任意一个位置出发，下一跳能够成的新区间右端点可能不同，当然要选右端点最大的那个，让整体覆盖范围推进得最快。

这里可以引出一个非常重要的全局观：整个算法维护两个边界，一个是当前这一跳的右边界 end，另一个是在 [0, end] 范围内所有位置出发，下一步能到达的最远位置 farthest。遍历下标 i 的过程，本质上是在当前区间内探查下一步的最大覆盖范围。当 i 走到 end 时，说明当前这一跳已经探查完毕，此时必须正式“起跳”，跳跃次数加一，把 end 更新为已经探查好的 farthest。

这个过程很像 BFS 的逐层扩展：end 是当前层的边界，farthest 是下一层的边界，每一跳就是一次从当前层到下一层的推进。理解了这一层，跳跃游戏II的代码就变得顺理成章。

3.3 核心代码与逐行解释

下面给出融合了区间覆盖思想的 C++ 实现。

int jump(vector<int>& nums) { int n = nums.size(); if (n <= 1) return 0; // 已经到达终点，不需要跳跃 int end = 0; // 当前这一跳能到达的右边界 int farthest = 0; // 在当前边界内，下一跳能到达的最远位置 int jumps = 0; // 跳跃次数 for (int i = 0; i < n - 1; i++) { // 站在 i 位置，更新下一跳可达的最远位置 farthest = max(farthest, i + nums[i]); // 当 i 走到当前这一跳的边界时，必须起跳 if (i == end) { jumps++; end = farthest; } } return jumps; }

几个关键点逐一说清楚。

第一，遍历范围是 i < n - 1。因为只要走到最后一个下标的前一个位置就已经完成了覆盖，最后一个位置本身不需要再被当作起跳点。如果写成 i < n，在某些情况下会在到达终点后又多触发一次跳跃，这是最常出现的边界错误。

第二，farthest 的更新必须在判断 i == end 之前。想象一下，当 i 到达 end 时，这个 i 本身也是一个可以起跳的位置，它产生的 i + nums[i] 也应该被算入下一跳的候选。如果先判断、后更新，会漏掉这个位置的潜力。

第三，jumps 的累加时机是“跨层”的时刻，也就是 i == end 时。这个时机实际上是区间覆盖里“每轮扫描结束，current 更新为 far”的另一种表现形式，只是它被压缩到了同一个循环里，理解起来不如独立一轮来得直观，但运行效率从 O(n^2) 级别优化到了 O(n)。

3.4 手动模拟一遍全过程

用最经典的测试用例 nums = [2, 3, 1, 1, 4] 走一遍，能很清楚地看到贪心推进覆盖点的全过程。

一开始 end = 0，farthest = 0，jumps = 0。

i = 0：farthest = max(0, 0 + 2) = 2。此时 i == end（0 == 0），触发跳跃，jumps = 1，end = 2。这代表着第一跳可以从 0 跳到最多下标 2。

i = 1：farthest = max(2, 1 + 3) = 4。下标 1 在 [0, 2] 这个范围内，它说明如果落脚点是 1，下一步能覆盖到下标 4。i 不等于 end，不触发跳跃。

i = 2：farthest = max(4, 2 + 1) = 4。i == end（2 == 2），触发跳跃，jumps = 2，end = 4。

此时循环结束，因为 i < n - 1，i 最大只能到 3。返回值是 jumps = 2，和题目预期一致。

如果把下标换成区间，整个覆盖过程是：第一步用区间 [0, 2]，第二步在第一步范围内找到一个能从位置 1 延伸到 4 的新区间，两步就完成了对终点 4 的覆盖。

4. 实战中的常见错误与调试技巧

4.1 最容易多算一次跳跃的边界问题

跳跃游戏II的代码非常短，但正因为短，边界错误很容易藏进去。我在实际讲解和带队时，见过最多的一类 bug 就是把循环写成这样：

for (int i = 0; i < n; i++) { farthest = max(farthest, i + nums[i]); if (i == end) { jumps++; end = farthest; } }

看起来只是把 i < n - 1 改成了 i < n，但在某些用例上会多算一次跳跃。比如 nums = [0] 时，n = 1，循环里 i = 0，i == end 成立，jumps 会变成 1，但正确答案显然是 0。即使对 nums = [1, 2] 这种正常用例，当 i = 1 等于 end 时执行跳跃，也会平白多跳一次。

我的建议有两个层面。第一是在函数开头加一个判空和单元素判断；第二是循环边界固定写成 i < n - 1，并且想清楚一件事：当前这一跳的 end 已经覆盖到了最后一个位置时，不需要再触发任何跳跃。如果实在怕写错，可以在这行附近写一行注释提醒自己。

4.2 为什么不能“谁当前跳得远就选谁”

还有一个非常常见的误解，就是把贪心决策理解成“每次都从当前位置跳到最远的地方”。这个理解在跳跃游戏I里勉强算对，因为第一题只问能不能到终点；但在跳跃游戏II里，它会直接导致答案错误。

举个例子 nums = [2, 3, 1, 1, 4]。如果第一步直接跳到最远下标 2，那么从下标 2 出发最多只能到下标 3，后面还需要一次跳跃，总次数可能是 3 次。而最优解是第一步先跳到下标 1，再利用下标 1 的跳跃能力直接到下标 4，总共只要 2 次。

原因在于，每一步真正要决策的不是“这次跳多远”，而是“这次跳完后，把下一步的覆盖范围撑到多大”。只看这一次的跳跃距离，是只顾眼前；而看这一次跳跃后下一步能覆盖多远，才是区间覆盖贪心真正的全局视角。这也是区间覆盖模型和“逐步最优”这种直觉之间的关键差距。

4.3 经典区间覆盖与跳跃游戏II的映射关系

把经典区间覆盖和跳跃游戏II放在一起对照，能更清晰地看到它们的统一性。

这个表格每到讲公开课时我都会放一遍，反馈是比单纯念代码有用得多。看懂了映射关系，跳跃游戏II就不是一道孤立题，而是区间覆盖专题里顺理成章的一个变体。

4.4 从 LeetCode 实测得到的两个小经验

在实际提交时，还有两个细节值得提。一是数组长度很大（比如 10 万甚至更长）时，int 类型的 end 和 farthest 完全够用，不需要考虑溢出，因为 i + nums[i] 最坏也就是 n + max(nums[i])，在题目范围内不会越界。二是这个解法本身已经是 O(n) 时间、O(1) 空间，网上有些动态规划版本需要 O(n) 的 dp 数组，除非题目额外要求“输出每次跳跃的下标”，否则没必要。

如果你需要输出路径，那就不能只维护 farthest 了，而是要在更新 farthest 时额外记下对应的起点下标。这个扩展思路留给感兴趣的读者自己实现，它本质上就是在区间覆盖中“记录每一步选择了哪个区间”的翻版。

5. 延伸思考：区间覆盖模型的边界与变形

5.1 当贪心失效时会发生什么

贪心算法不是万能钥匙，区间覆盖模型也一样。最容易让人误解的是它和“最多不相交区间”问题的差别。后者是经典的区间调度问题，策略是按右端点排序、依次选择最早结束的区间，目标是最多能选多少个互不重叠的区间；而区间覆盖是按左端点排序、选择右端点最远者，目标是最少区间覆盖整段。如果拿错了排序方向或者选错了贪心依据，结果会差得很远。

举一个直观的反例。目标区间是 [1, 10]，候选区间有 [1, 3]、[2, 8]、[4, 9]、[7, 10]。如果按“每次选最短区间”的思路，第一步可能选了 [2, 8]（长度 6，看起来覆盖比较长），但它从 2 开始，无法覆盖到位置 1，这就直接断档了。即使第一步选 [1, 3]，后面为了接上 [3, 10]，也需要两到三个区间，最终数量会超过最优解。贪心策略对“按什么指标选”极其敏感，这也是为什么不能靠死记硬背、而必须理解贪心依据背后的证明。

另一个隐藏的失效场景是覆盖点推进出现“断档”却没被及时检测。在经典区间覆盖里，如果某轮扫描结束 far 没有超过 current，说明无法覆盖，立刻返回。在跳跃游戏II里，如果题目不保证能到达终点，就需要在循环结束后判断 farthest 是否仍然小于 n - 1，若是则返回 -1。这是我建议在做变体题时额外留意的。

5.2 从竞赛题到工程建模

区间覆盖模型在竞赛之外，最典型的应用是基站选址和物联网覆盖规划。比如在设计一个低功耗广域网时，一个网关节点能覆盖的范围就是一个以网关为中心、以通信距离为半径的圆形区域，分布在道路或河道旁的节点就可以把这些圆形区域投影成数轴上的覆盖区间。工程上通常不会直接暴搜所有组合，而是先把离散的覆盖范围转成区间，再用贪心跑一版近似方案，效率会高很多。

另一个工程场景是云端任务调度里的“时间片覆盖”。当一个任务允许在多个时间窗口内执行，而需求方要求业务在连续某段时间内始终有可用的执行时机时，每个可选时间窗口就是一个小区间，目标是选出最少窗口拼出完整连续时间，这和洒水装置覆盖马路本质上是同一个问题。把这些案例放在一起，会发现区间覆盖的普适性远超竞赛题本身。

值得一提的是，当候选区间数量级很大、且区间端点范围也很大时，可以用线段树配合离散化来做区间更新和覆盖点查询，但那是另一个层面的优化了，日常训练阶段先用好贪心的一维扫描足够解决绝大多数问题。

最后，我想分享一个这段时间反复验证的个人观点：贪心算法真正难的地方不是“想到贪心”，而是“验证这个贪心确实是对的”。区间覆盖这个模型之所以适合做入门题，是因为它的正确性证明非常朴实，逻辑链条短，适合拿来建立“贪心题敢想、也敢证明”的底气。等后面遇到跳跃游戏II这种表面变化很大的题，再回看这些基础模型，你会更容易识别出它们的共同骨架。如果这篇文章能帮你把跳跃游戏II从“动态规划脑”切换到“区间覆盖脑”，那这次整理就没有白费。