贪心 · 区间问题

1. 核心原理

区间贪心是一类以"区间集合"为输入、要求做"选/删/合并/覆盖"决策的题目。给定 n 个区间 [lᵢ, rᵢ]，常见问法有三种主线：

1. 选最多不重叠区间（等价于"删最少区间剩余互不重叠"）—— LC 435 / 452
2. 合并所有重叠区间为不相交集合 —— LC 56 / 57
3. 用最少的点/区间覆盖给定范围 —— LC 452 / 1326

这三种问法都可以用 O(n²) 或 O(n log n) DP 解，但贪心解都只需要 O(n log n) 排序 + O(n) 一遍线性扫，写法更短、常数更小。其核心做法仅两条：

• 按右端点升序排序 —— 解第一类（选最多 / 删最少 / 最少箭）
• 按左端点升序排序 —— 解第二类（合并相邻）

第三类是上面两条的混合。本章只把这两条吃透。

暴力为什么不够

第一类问法的朴素解是枚举 intervals 的所有子集，看哪个最大不重叠子集的大小。O(2ⁿ · n)，n = 10⁵ 直接 TLE。退一步用 DP：按某序排序后用 LIS 套路求"最长不重叠子序列"，能压到 O(n²) 或 O(n log n)。但贪心解避开了 DP 的状态空间，直接一遍扫——是这类题的标准答案。

关键洞察：按右端点排序的最优性

第一类问法（选最多不重叠）的贪心是：按右端点升序排序，从左到右扫，能选就选——只要当前区间的左端点不小于上一个已选区间的右端点（"相邻不算重叠"语义下取 ≥，"必须严格分离"语义下取 >）。

直觉上：右端点越早结束，给后续留出的可用空间越大，选它的"代价"最小。严格证明用交换论证：

设最优解 OPT 中第一个被选的区间是 X = [a, b]。令 Y = [c, d] 为右端点最小的区间，d ≤ b。分两种情况：

• Y ∉ OPT：把 OPT 里的 X 换成 Y。由于 d ≤ b，后续与 X 不冲突的区间也必与 Y 不冲突。|OPT| 不变。
• Y ∈ OPT 但 Y 不是第一个：那 Y 排在 X 之后，须有 c ≥ b。结合 d ≤ b ≤ c 得 d ≤ c，但区间合法要求 c < d，矛盾。所以 Y 必须能放到第一个位置。

任何最优解都能调整成"第一个区间是右端点最小的那个"。对剩余区间归纳即可——贪心选右端点最小的总能给出最优解。

关键洞察：按左端点排序的最优性

第二类问法（合并区间）的贪心是：按左端点升序排序，维护一个 result 栈/列表，逐区间检查能否与栈顶合并。若当前区间左端点不大于栈顶右端点，就把栈顶右端点扩张为 max(栈顶.r, 当前.r)；否则当前区间另起一个新分量。

为何按左端点排序就够？按左端点排序后，相邻两区间只有两种可能：① 当前区间左端点 > 栈顶右端点 ——必须分开；② 当前区间左端点 ≤ 栈顶右端点 ——必合并，且合并后右端点为 max。所有传递性合并都能被这一次扫到——不会出现"两个远端区间中间还能桥接"的漏判。

两类问法对照

容易混淆的相邻题

• LC 252 / 253 会议室 / 会议室 II：判断"能不能全部开完"（252）按左端点扫；"最少几间会议室"（253）有两种主流解——事件法（开始 +1、结束 −1），或按左端点排序 + 最小堆维护当前所有占用会议室的最早结束时间。
• LC 1326 灌溉花园：先把"中心 + 范围"转成区间，再变成"用最少区间覆盖 [0, n]"——按左端点排序后贪心扩展可达右端点。
• LC 452 戳气球箭：与 LC 435 同型贪心（按右端点排序），细节差异在"相邻是否算重叠"的取等号问题——见 §5 边界。

与 DP 解法的复杂度对照

贪心解与 LIS+二分同阶，但常数小、代码短，是首选写法。

2. 通用模板

下面两段模板分别对应"选最多不重叠"和"合并相邻"两类问法。三种语言接口一致：输入 intervals（二维数组），输出整数或合并后的二维数组。

# 模板一：按右端点排序，选最多不重叠
def max_non_overlapping(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])               # 关键：按 end 升序
    prev_end = float('-inf')                         # 已选区间的最右端点
    count = 0
    for start, end in intervals:
        if start >= prev_end:                        # 相邻不算重叠 → ≥；严格分离 → >
            count += 1                               # 选当前
            prev_end = end                           # 更新阈值
    return count


# 模板二：按左端点排序，合并区间
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])               # 关键：按 start 升序
    result: list[list[int]] = []
    for start, end in intervals:
        if result and start <= result[-1][1]:        # 与上一段有重叠 → 合并
            result[-1][1] = max(result[-1][1], end)
        else:                                        # 不重叠 → 另起新段
            result.append([start, end])
    return result

// 模板一：按右端点排序，选最多不重叠
int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);    // 关键：按 end 升序
    int prevEnd = Integer.MIN_VALUE, count = 0;
    for (int[] iv : intervals) {
        if (iv[0] >= prevEnd) {                       // 相邻不算重叠时取 ≥
            count++;                                  // 选当前
            prevEnd = iv[1];                          // 更新阈值
        }
    }
    return count;
}

// 模板二：按左端点排序，合并区间
int[][] mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);    // 关键：按 start 升序
    List<int[]> result = new ArrayList<>();
    for (int[] iv : intervals) {
        if (!result.isEmpty() && iv[0] <= result.get(result.size() - 1)[1]) {
            result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], iv[1]);
        } else {
            result.add(iv);
        }
    }
    return result.toArray(new int[0][]);
}

// 模板一：按右端点排序，选最多不重叠
int maxNonOverlapping(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });   // 按 end 升序
    int prevEnd = INT_MIN, count = 0;
    for (auto& iv : intervals) {
        if (iv[0] >= prevEnd) {                       // 相邻不算重叠时取 ≥
            count++;
            prevEnd = iv[1];
        }
    }
    return count;
}

// 模板二：按左端点排序，合并区间
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });   // 按 start 升序
    vector<vector<int>> result;
    for (auto& iv : intervals) {
        if (!result.empty() && iv[0] <= result.back()[1]) {
            result.back()[1] = max(result.back()[1], iv[1]);
        } else {
            result.push_back(iv);
        }
    }
    return result;
}

骨架几个要点：

• 排序键决定一切：模板一按 end 升序、模板二按 start 升序，是两类问法各自最优性的来源。把排序键写错（比如模板一按 start），样例 [[1,100],[2,3],[3,4]] 立刻给出错误答案 1（应为 2）。
• 取等号方向：模板一里 iv[0] >= prevEnd 还是 > 取决于题面对"相邻"的定义。LC 435 / 56 把 [1,2] 与 [2,3] 视作不重叠（用 ≥），LC 252 / 253 视作冲突（用 >）——读题时第一件事是看示例确认。
• 模板一只需常数辅助空间：prev_end 和 count，不需要保存被选区间本身。如果要还原出"选了哪些区间"，再额外维护一个 chosen 列表即可。
• 模板二要把 result.back()[1] 更新成 max：朴素地写 result.back()[1] = end 会在样例 [[1,10],[2,3]] 上把 [1,10] 合并成 [1,3]，丢掉外层的右端点 10。
• 复杂度：两段模板都是 O(n log n) 排序 + O(n) 扫描；额外空间 O(1)（模板一）或 O(n)（模板二的 result）。

3. 母题精讲

LeetCode 435. 无重叠区间

链接：LeetCode 435

题意：给一个区间集合 intervals，每个区间是 [start, end]。返回需要移除的最少区间数量，使剩下的区间互不重叠。注意"相邻不算重叠"（[1, 2] 和 [2, 3] 不重叠）。

数据范围：

• intervals.length：1 到 10⁵
• −5 × 10⁴ ≤ start < end ≤ 5 × 10⁴

示例：

输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
输出：1
解释：移除 [1,3] 后，剩下 [1,2], [2,3], [3,4] 互不重叠。

输入：intervals = [[1,2],[1,2],[1,2]]
输出：2

问题改写为等价形式：

求最多能选多少个互不重叠的区间。设最多 k 个，答案 = n − k。

这正是 §2 模板一的形式。下面交互演示走一遍 intervals = [[1,2],[2,3],[3,4],[1,3]] 按右端点排序后的贪心：

最少移除 1 个（即 [1,3]）。复杂度 O(n log n) 排序 + O(n) 扫描。完整代码见 §4.1。

4. 例题（三道）

4.1 LC 435 无重叠区间

回到本章开头那道题。直接套"按右端点排序 + 选最多"模板：

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        prev_end = float('-inf')
        kept = 0
        for s, e in intervals:
            if s >= prev_end:
                kept += 1
                prev_end = e
        return len(intervals) - kept

复杂度 O(n log n) 排序 + O(n) 扫描，毫秒级。

Follow-up：把"剩下区间互不重叠"换成"用最少多少根箭射穿所有气球（气球范围 = 区间，相邻区间相切算同一箭）"，问的变成"最少需要几根箭"——这就是 LC 452，同款模板。

4.2 LC 452 用最少数量的箭引爆气球

链接：LeetCode 452

题意：给一组气球的水平投影区间 points[i] = [x_start, x_end]。一根垂直方向的箭在 x 处发射，会引爆所有满足 x_start ≤ x ≤ x_end 的气球。返回引爆所有气球所需的最少箭数。

数据范围：

• points.length：1 到 10⁵
• −2³¹ ≤ x_start < x_end ≤ 2³¹ − 1

示例：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：箭 x=6 引爆 [2,8] 和 [1,6]，箭 x=11 引爆 [10,16] 和 [7,12]。

思路：跟 LC 435 几乎一模一样——"选最多互不重叠"的对偶是"分组"，每根箭对应一组互相重叠的气球。注意区别：LC 435 用 s >= prev_end（相邻不算重叠），LC 452 用 s > prev_end（相切的气球也能一起引爆）。

class Solution:
    def findMinArrowShots(self, points: list[list[int]]) -> int:
        points.sort(key=lambda x: x[1])
        arrows = 1
        prev_end = points[0][1]
        for s, e in points[1:]:
            if s > prev_end:                       # 相切不算 → 用 >
                arrows += 1
                prev_end = e
        return arrows

复杂度 O(n log n)。

数据范围陷阱：x_start 和 x_end 可能是 −2³¹、2³¹ − 1。Java 的 a[1] - b[1] 比较器会 overflow，必须用 Integer.compare(a[1], b[1])。Python / Go 大整数无忧。

Follow-up：上面两题都是按右端点排序"剔/分"。如果题目反过来要"把若干区间合并成最少不重叠的几个区间"呢——这就是 LC 56，要按左端点排序。

4.3 LC 56 合并区间

链接：LeetCode 56

题意：给一个区间数组 intervals，合并所有重叠的区间，返回合并后的区间数组。

数据范围：

• intervals.length：1 到 10⁴
• 0 ≤ start ≤ end ≤ 10⁴

示例：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：[1,3] 和 [2,6] 重叠，合并为 [1,6]。

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]

思路：按左端点排序。维护一个 result 列表，对每个新区间 [s, e]：

• 如果 result 非空且 s ≤ result[-1].end（重叠），把 result[-1] 的 end 更新为 max(result[-1].end, e)
• 否则把 [s, e] 加到 result 末尾

数轴可视化 [[1,3],[2,6],[8,10],[15,18]] 排序后的合并过程：

位置:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18

排序后输入:
         ▢━━━▢                              [1, 3]
            ▢━━━━━━━━━▢                     [2, 6]   ← 与 [1,3] 重叠
                              ▢━━━▢         [8, 10]
                                          ▢━━━▢   [15, 18]

合并扫描:
Step 1:  ▢━━━▢                              result = [[1, 3]]
Step 2:  ▢━━━━━━━━━━━━▢                     result = [[1, 6]]    (2 ≤ 3 重叠，end = max(3, 6))
Step 3:  ▢━━━━━━━━━━━━▢   ▢━━━▢             result = [[1, 6], [8, 10]]   (8 > 6 不重叠)
Step 4:  ▢━━━━━━━━━━━━▢   ▢━━━▢   ▢━━━▢     result = [[1, 6], [8, 10], [15, 18]]

输出: [[1, 6], [8, 10], [15, 18]]

判别"重叠"只看相邻两个：因为按左端点排序后，如果 i 和 i+1 不重叠，那 i+1 之后的区间左端点更靠右、更不可能与 i 重叠——所以扫描只关心"当前新区间"和"result 末尾那个"即可。

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort(key=lambda x: x[0])
        result = []
        for s, e in intervals:
            if result and s <= result[-1][1]:
                result[-1][1] = max(result[-1][1], e)
            else:
                result.append([s, e])
        return result

复杂度 O(n log n)。

关键细节：合并后的 end 是 max(result[-1].end, e)，不是简单的 e——因为输入是 [[1, 10], [2, 5]] 时，合并后 end 还是 10 不是 5。

5. 边界、易错与复杂度

"相邻是否算重叠"

LC 435 把 [1, 2] 和 [2, 3] 当不重叠（用 s >= prev_end）；LC 452 把它们当重叠（用 s > prev_end，相切可一起射）；LC 56 也把相邻区间合并（用 s <= prev_end，相切的也并起来）。题目数据语义不一样，写代码前必须看清楚。

判断条件速查：

排序比较器的 overflow

LC 452 的 [x_start, x_end] 在 Java 写 (a, b) -> a[1] - b[1] 会 overflow（2³¹ − 1 − (−2³¹) 溢出）。改用 Integer.compare(a[1], b[1])。Python / Go 没这问题。

空数组 / 单元素

模板要兼容空输入：

if not intervals:
    return 0   # 或 []

合并模板里 if result and s <= result[-1][1] 自然处理空 result 情况。

复杂度速查

为什么都是 O(n log n)：排序是瓶颈，扫描部分只跑一遍 = O(n)，合起来 O(n log n + n) = O(n log n)。

什么时候能降到 O(n)：

• 输入已按需要的 key 排序——如 LC 57（插入区间，给的就是排好的区间），跳过排序直接扫描，O(n)
• 值域可以桶排序 / 计数排序——如 LC 1326（区间端点 ≤ n），直接开桶数组，省掉 log 因子
• 事件法 + 桶：把 (start, +1) / (end, -1) 事件按值域分桶 → O(V + n)，V 是值域大小，V = O(n) 时整体 O(n)

实战中 n ≤ 10⁵ 量级 O(n log n) 完全够用，只有 n ≥ 10⁷ 或卡内存的题才追求 O(n)。

7. 小结

区间贪心的两个维度——按右端点（选最多 / 删最少 / 分组）和按左端点（合并 / 覆盖）。哪种问法用哪种排序键，记住后多数区间题都能套模板。证明贪心正确性靠交换论证，"按右端点排序 + 不冲突就选"在选最多问题上总是最优。

对应灵神题单：贪心入门 / 区间贪心 / 排序贪心

进一步阅读：LeetCode 贪心题单 / 灵茶山艾府贪心专题