区间贪心与覆盖模型 (Interval Greedy & Coverage)¶

区间问题（Interval Problems） 是各大互联网公司技术面试与算法竞赛中最常考的贪心模型。

区间通常由左端点 \(start\) 和右端点 \(end\) 构成。这类问题的核心解题密码在于：“明确排序基准（按左端点还是右端点排序） + 维护前沿状态变量”。

1. 核心排序策略与选型逻辑¶

面对区间问题，首要决策是排序方式：

排序策略	核心直觉与适用场景	经典问题模型
按右端点升序排序	越早结束的区间，给后续区间留下的空闲时间轴越宽广	不相交区间最大化、最少点覆盖所有区间
按左端点升序排序	优先处理最先开始的区间，方便向右合并或延伸覆盖	区间合并、区间完全覆盖（视频拼接）、区间分组（会议室）

区间重叠与覆盖关系：
[--- Interval A ---]
         [--- Interval B ---]          (重叠: B.start < A.end)
                               [--- C ---] (不相交: C.start >= B.end)

2. 经典区间贪心模型详解与模板¶

2.1 模型一：不相交区间最大化 (Interval Scheduling)¶

问题：给定一组区间，选出互不重叠的区间的最大数量（或求移除最少区间使得剩余区间互不重叠）。

贪心策略与保持前沿法证明：¶

排序：按右端点（结束时间）升序排序；
选择：总是贪心选择当前剩余区间中结束时间最早且与前一个选择不冲突的区间；
证明：设贪心选出的第 \(i\) 个区间的结束时间为 \(g_i\)，任意最优解选出的第 \(i\) 个区间结束时间为 \(o_i\)。由贪心规则，必有 \(g_i \le o_i\)。由于 \(g_i\) 留给后续区间的空间 \([g_i, +\infty)\) 严格包含 \(o_i\) 留下的空间 \([o_i, +\infty)\)，因此贪心解能容纳的区间总数必定不少于任何最优解！详细数学归纳与反证推导可参阅：👉 保持前沿法 (Staying Ahead) 保姆级证明。

#include <vector>
#include <algorithm>

int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // 1. 按右端点升序排序
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });

    int count = 1; // 选出的最多互不重叠区间数
    int last_end = intervals[0][1];

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] >= last_end) {
            count++;
            last_end = intervals[i][1];
        }
    }
    // 移除最少数量 = 总数 - 最多保留数
    return static_cast<int>(intervals.size()) - count;
}

2.2 模型二：最少点覆盖所有区间 (Minimum Arrows)¶

问题：给定若干区间，在数轴上放置最少数量的点（或发射最少数量的箭），使得每个区间内至少包含一个点。

贪心策略：¶

按右端点升序排序；
第一支箭射在第一个区间的右端点 \(pos = intervals[0][1]\) 处（越靠右，越有可能穿透后续的重叠区间）；
遍历后续区间：若当前区间的左端点 \(\le pos\)，说明这支箭可以一并引爆它；若左端点 \(> pos\)，说明必须追加一支新箭，并将发射位置更新为当前区间的右端点。

2.3 模型三：区间完全覆盖 (Minimum Interval Covering)¶

问题：用最少数量的区间完全覆盖目标线段 \([0, T]\)。若无法完全覆盖则返回 \(-1\)。

贪心策略：¶

维护当前已经完全覆盖的右边界 \(curr\_end\) 与下一步能探索到的最远右边界 \(max\_reach\)；
在所有左端点 \(\le curr\_end\) 的候选区间中，贪心地选择右端点最大的区间；
若 \(max\_reach \ge T\)，说明已成功覆盖全段；若候选区间都无法超越 \(curr\_end\)，说明中间出现断层，无解返回 \(-1\)。

3. LeetCode 经典真题精选与深度精析¶

LeetCode 435 - 无重叠区间 (Non-overlapping Intervals) 中等
提示

不相交区间最大化基石题。
- 求移除区间的最小数量 \(\iff\) 数组总长减去“最大互不重叠区间数”。
- 按区间右端点升序排序。遍历数组，若当前区间左端点 \(\ge\) 上一个被保留区间的右端点，则保留该区间并更新右端点；否则计入移除计数。
- 时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(1)\)。
LeetCode 452 - 用最少数量的箭引爆气球 (Minimum Number of Arrows to Burst Balloons) 中等
提示

区间交集收缩贪心。
- 按右端点升序排序。
- 箭的坐标初始化为第一个气球的右边界。后续只要气球左端点大于当前箭的坐标，就必须消耗一支新箭并更新位置。
- 防溢出细节：比较器中不要直接写 a[1] - b[1]（可能会因负数引发整数溢出），应严格使用 < 比较。
LeetCode 56 - 合并区间 (Merge Intervals) 中等
提示

按左端点升序排序的连续合并模型。
- 按左端点升序排序。
- 维护当前合并区间的左右端点 \([L, R]\)。遍历下一个区间 \([start, end]\)：
- 若 \(start \le R\)，说明两区间重叠，贪心扩展右边界：\(R = \max(R, end)\)；
- 若 \(start > R\)，说明两区间断开，将 \([L, R]\) 推入答案，并开启新区间 \([start, end]\)。
- 严格 \(\mathcal{O}(N \log N)\) 排序时间，\(\mathcal{O}(N)\) 结果空间。
LeetCode 1024 - 视频拼接 (Video Stitching) 中等
提示

区间完全覆盖与跳跃游戏转化。
- 预处理数组 max_reach[i] 表示以 \(i\) 为起点的区间能到达的最远右端点。
- 维护当前这一跳覆盖的右边界 curr_end 与下一步能到达的最远边界 next_end。
- 遍历 \(i \in [0, time - 1]\)：
- 动态更新 next_end = max(next_end, max_reach[i])；
- 当 \(i == curr\_end\) 时，步数加 1（steps++），并将边界推至 curr_end = next_end；
- 若某时刻 \(i \ge next\_end\)，说明出现断层无法前进，返回 \(-1\)。
LeetCode 763 - 划分字母区间 (Partition Labels) 中等
提示

字符最远出现下标与贪心切分窗口。
- 题目要求同一个字母最多出现在一个片段中。
- 预处理数组 last[c] 记录每个字符在全串中最后出现的绝对下标。
- 维护当前片段的起始指针 start 与必须扩展到的最右端点 end。
- 遍历字符串：当前字符的最远位置为 last[s[i]]，贪心更新 end = max(end, last[s[i]])。
- 当遍历下标 \(i == end\) 时，说明当前窗口内所有字母在之后绝不再出现，在此处果断切分，记录长度 end - start + 1，并更新 start = end + 1。
LeetCode 2406 - 将区间分为最少组数 (Divide Intervals Into Minimum Number of Groups) 中等
提示

区间分组与最小堆维护 / 差分数组扫描线。
- 两个区间若重叠则不能分在同一组。求最少组数 \(\iff\) 求数轴上任意点被区间覆盖的最大重叠次数（最大交叠层数）。
- 解法一（贪心 + 最小堆）：
- 按左端点升序排序；
- 小顶堆维护当前每个组的“最晚结束时间”；
- 遍历区间：若当前区间左端点大于堆顶，说明可以复用堆顶那个组，弹出堆顶并压入当前区间的右端点；否则必须新开一组，直接压入当前右端点。最终堆大小即为答案。
- 解法二（差分数组 / 事件扫描线）：
- 左端点记为 \(+1\) 事件，右端点 \(+1\) 记为 \(-1\) 事件；
- 排序后扫描求前缀和最大值，时间复杂度 \(\mathcal{O}(N \log N)\)。
LeetCode 57 - 插入区间 (Insert Interval) 中等
提示

有序区间三段式单遍扫描合并。
- 给定原本已经排好序且互不重叠的区间列表，插入新区间 newInterval = [start, end] 并保持无重叠有序。
- 无需重新排序（避免 \(\mathcal{O}(N \log N)\)），直接三段式贪心单遍扫描（\(\mathcal{O}(N)\) 线性时间）：
- 左侧不重叠部分：若当前区间右端点 \(< start\)，完全在新区间左侧，直接加入结果；
- 中间重叠部分：若当前区间左端点 \(\le end\)，说明与新区间存在交集，贪心扩展新区间边界：start = min(start, interval[0]), end = max(end, interval[1])；
- 将合并后的新区间压入结果，并将剩余右侧不重叠区间依次加入。
LeetCode 1326 - 灌溉花园的最少水龙头数目 (Minimum Number of Taps to Open to Water a Garden) 困难
提示

线段覆盖转化为跳跃游戏 II。
- 水龙头 \(i\) 能覆盖的区间为 \([\max(0, i - ranges[i]), \min(n, i + ranges[i])]\)。
- 目标：用最少水龙头完全覆盖 \([0, n]\)。
- 预处理转换：定义 max_reach[left] 表示以 left 为左边界的所有水龙头中，能够延伸到的最远右边界。
- 转化为标准跳跃游戏 II：维护当前步能覆盖的右边界 curr_end 与下一步能到达的最远边界 next_end，若到达 curr_end 则水龙头数量加 1 并更新边界；若出现断层则无解返回 \(-1\)。
- 时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(N)\)。
LeetCode 646 - 最长数对链 (Maximum Length of Pair Chain) 中等
提示

按右端点升序排序的区间调度贪心映射。
- 数对 \((a, b)\) 可以接在 \((c, d)\) 后面当且仅当 \(b < c\)。
- 本质完全等价于不相交区间最大化（LeetCode 435）！
- 贪心策略：按数对的第二个数（右端点）升序排序。总是选择结束最早且与前一个数对不重叠的数对，为后续留下最大的数值增长空间。
- 时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(1)\)。