跳到主要内容

AcWing 907. 区间覆盖

本节目标

每轮选取可接续区间中右端点最远者，最少覆盖指定目标区间。

这是区间排序与调度中“最大化连续前缀”的母题。

查看 AcWing 原题

题意与约束​

给定闭区间集合和目标闭区间 [left,right]，求完整覆盖正长度目标线段所需的最少区间数。若在某处出现缺口，返回 -1；按本教程约定，left >= right 表示无需覆盖，返回 0。

直接思路与瓶颈​

枚举所有区间子集再验证联合是否连续，组合数量不可承受。每次挑第一个左端点可接上的区间也可能走得太短，后面被迫多选甚至遇到本可避开的缺口。

贪心模型与算法推导​

按左端点升序排序，维护已连续覆盖到的最右位置 covered。在所有 l <= covered 的区间中扫描出最大右端点 farthest，选择它并令 covered=farthest。若这一轮没有任何区间让 covered 变大，说明当前点右侧没有可接续区间，立即返回 -1。

正确性依据​

任何覆盖方案的下一段必须从不晚于 covered 的位置开始，否则在 covered 后立刻留下缺口。设某个最优方案下一段的右端点为 x，贪心在同一批可接续区间中选到 farthest >= x。把该段替换为贪心区间后，已覆盖前缀不缩短，剩余方案仍可接续且使用区间数不增。因此存在最优方案先走到 farthest。重复该替换，直到覆盖 right；若无法推进，则任何方案都不能连续越过缺口。

样例执行过程​

目标为 [0,8]，区间为 [-1,3]、[2,5]、[4,8]。

  1. covered=0，可接续的只有 [-1,3]，选择后到 3。
  2. covered=3，[2,5] 可接续，选择后到 5。
  3. covered=5，[4,8] 可接续，选择后到 8。

使用三段刚好覆盖目标，答案为 3。

代码实现​

C++17
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int minCoverIntervals(vector<pair<int, int>> intervals, int left, int right) {
    if (left >= right) return 0;

    sort(intervals.begin(), intervals.end());
    int index = 0;
    int covered = left;
    int count = 0;

    while (covered < right) {
        int farthest = covered;
        while (index < static_cast<int>(intervals.size()) && intervals[index].first <= covered) {
            farthest = max(farthest, intervals[index].second);
            ++index;
        }
        if (farthest == covered) return -1;
        covered = farthest;
        ++count;
    }
    return count;
}

复杂度分析​

排序后指针只前进不回退，时间为 O(n log n)，排序副本使用 O(n) 空间。

边界与易错点​

  • 只接受 l <= covered 的区间；l > covered 已经越过缺口。
  • farthest == covered 表示不能推进，返回 -1；left >= right 则按约定直接返回 0。
  • 闭区间端点相等可以接续：[0,2] 和 [2,5] 能共同覆盖 [0,5]。
  • 不能仅因读到一个候选就作决定，必须比较本轮全部可接续区间。

模式迁移​

视频剪辑、灌溉花园和跳跃覆盖等问题都会把“当前位置”改写为连续覆盖前缀。只要下一段必须从当前边界之前开始，就可以沿用每轮取最远右端点的交换论证。