区间问题：一套排序，解决一类题

先排好，再扫一遍——区间问题的答案往往就在这两步里。

写在前面

区间问题可以说是 LeetCode 里自成一体的一个题系。题目说法各异——合并区间、插入区间、无重叠区间、射气球——但大体上都绕不开两类排序思路：

  1. 合并 / 插入类：按左端点排序，从左到右扫描，维护一个「当前区间」
  2. 选择 / 贪心类：按右端点排序，优先保留结束更早的区间

理解了“该按哪一端排序”，这类题基本都能自己推出来，不需要死记模板。

区间的基本概念

一个区间用 [l, r] 表示从 l 到 r 的连续范围。两个区间的关系只有三种：

1
2
3
4
5
6
7
8
区间 A: [───────]
区间 B:             [────]     → 不相交（B 在 A 右边）

区间 A: [───────]
区间 B:       [────]           → 相交（有重叠部分）

区间 A: [───────────]
区间 B:    [─────]             → A 包含 B

判断两个区间 [a, b] 和 [c, d] 是否相交（含端点）：

1
2
相交条件：a <= d && c <= b
不相交条件：b < c || d < a

这个条件记住，后面反复用到。

例题讲解

例题一：合并区间（LeetCode 56）

给出一组区间，合并所有重叠的区间，返回合并后的结果。

输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

问题分析：

多个区间可能互相重叠，需要把能连成一片的都合并掉。难点在于区间顺序是乱的，不排序很难判断哪些能合并。

思路：

先按左端点排序，然后从左往右扫，维护一个「当前正在合并的区间」[cur_l, cur_r]：

  • 如果下一个区间的左端点 ≤ cur_r，说明有重叠，把右端点更新为 max(cur_r, next_r)
  • 否则，当前区间合并完毕，把它存入结果，开始处理下一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    // 按左端点排序
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> res;
    int cur_l = intervals[0][0];
    int cur_r = intervals[0][1];

    for (int i = 1; i < (int)intervals.size(); i++) {
        int l = intervals[i][0], r = intervals[i][1];
        if (l <= cur_r) {
            // 有重叠，扩展右端点
            cur_r = max(cur_r, r);
        } else {
            // 无重叠，保存当前区间，移动到下一个
            res.push_back({cur_l, cur_r});
            cur_l = l;
            cur_r = r;
        }
    }
    res.push_back({cur_l, cur_r});  // 别忘了最后一个区间

    return res;
}

执行过程：

1
2
3
4
5
6
7
8
9
10
输入（排序后）：[1,3] [2,6] [8,10] [15,18]

初始：cur = [1, 3]

i=1: [2,6]，2 <= 3，有重叠 → cur = [1, max(3,6)] = [1, 6]
i=2: [8,10]，8 > 6，无重叠 → 保存 [1,6]，cur = [8, 10]
i=3: [15,18]，15 > 10，无重叠 → 保存 [8,10]，cur = [15, 18]
结束：保存 [15, 18]

结果：[[1,6], [8,10], [15,18]]

复杂度：

  • 时间：O(n log n)，排序主导
  • 空间：O(n)，结果数组

例题二：插入区间（LeetCode 57）

给定一组已经排好序且不重叠的区间，插入一个新区间，返回合并后的结果。

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]，newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]

问题分析：

区间已经有序，不需要重新排序。插入新区间后，它可能和一批已有区间重叠，需要统一合并。

思路：

分三段处理：

  1. 把所有在新区间左边（完全不重叠）的区间直接放进结果
  2. 与新区间有重叠的区间，全部合并进去
  3. 剩下在右边的区间直接放进结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<vector<int>> insert(vector<vector<int>>& intervals,
                           vector<int>& newInterval) {
    vector<vector<int>> res;
    int i = 0, n = intervals.size();

    // 第一段：在新区间左边，完全不重叠
    while (i < n && intervals[i][1] < newInterval[0]) {
        res.push_back(intervals[i++]);
    }

    // 第二段：有重叠，统一合并
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);  // 扩展左端点
        newInterval[1] = max(newInterval[1], intervals[i][1]);  // 扩展右端点
        i++;
    }
    res.push_back(newInterval);  // 合并后的新区间入队

    // 第三段：在新区间右边，完全不重叠
    while (i < n) {
        res.push_back(intervals[i++]);
    }

    return res;
}

执行过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4, 8]

第一段：
  [1,2]：2 < 4，在左边 → 直接放入结果
  [3,5]：5 >= 4，停止

第二段（有重叠）：
  [3,5]：3 <= 8，重叠 → new = [min(4,3), max(8,5)] = [3, 8]
  [6,7]：6 <= 8，重叠 → new = [min(3,6), max(8,7)] = [3, 8]
  [8,10]：8 <= 8，重叠 → new = [min(3,8), max(8,10)] = [3, 10]
  [12,16]：12 > 8，停止
放入 [3, 10]

第三段：
  [12,16] 直接放入

结果：[[1,2], [3,10], [12,16]]

复杂度：

  • 时间：O(n)，只扫一遍
  • 空间：O(n)

例题三：无重叠区间（LeetCode 435）

给定一组区间，找出需要移除的最少区间数量，使得剩余区间互不重叠。

输入：[[1,2],[2,3],[3,4],[1,3]]
输出：1（移除 [1,3]）

问题分析：

移除最少，等价于保留最多不重叠的区间，然后用总数减去保留数。

贪心思路：

这是经典的「区间调度」问题。贪心策略是按右端点排序，每次在不冲突的前提下优先选右端点最小的区间——这样给后续区间留的空间最多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    // 按右端点排序（贪心关键）
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    int keep = 1;            // 至少保留第一个
    int last_r = intervals[0][1];  // 当前已选区间的右端点

    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] >= last_r) {
            // 不冲突，可以保留
            keep++;
            last_r = intervals[i][1];
        }
        // 冲突就跳过（相当于移除）
    }

    return (int)intervals.size() - keep;  // 总数 - 保留数 = 移除数
}

为什么按右端点排序，而不是左端点？

1
2
3
4
5
6
7
8
9
10
11
12
反例：按左端点排序
区间：[1, 100], [2, 3], [4, 5]
         ↑ 左端点最小但右端点极大，一旦选它，后面全冲突

按右端点排序：
区间：[2, 3], [4, 5], [1, 100]
先选 [2,3]，再选 [4,5]，[1,100] 冲突跳过
→ 保留 2 个，移除 1 个（正确）

按左端点排序：
先选 [1,100]，[2,3] 冲突，[4,5] 冲突
→ 保留 1 个，移除 2 个（错误）

执行过程：

1
2
3
4
5
6
7
8
9
输入（按右端点排序后）：[1,2] [2,3] [1,3] [3,4]

初始：keep=1，last_r=2

i=1: [2,3]，2 >= 2，不冲突 → keep=2，last_r=3
i=2: [1,3]，1 < 3，冲突 → 跳过
i=3: [3,4]，3 >= 3，不冲突 → keep=3，last_r=4

移除数 = 4 - 3 = 1

复杂度：

  • 时间：O(n log n)
  • 空间：O(1)

例题四：用最少数量的箭引爆气球（LeetCode 452）

每个气球用区间 [x_start, x_end] 表示其水平范围，一支箭可以引爆所有覆盖该 x 坐标的气球。
求最少需要多少支箭。

输入：[[10,16],[2,8],[1,6],[7,12]]
输出：2

问题分析：

这和「保留最多不重叠区间」是同一类贪心，只是问法从「移除多少」变成了「需要几组」。每一支箭对应一组互相重叠的区间，最少箭数 = 最多不重叠的区间组数。

注意这道题里端点相等也算重叠（箭从 x=6 能同时引爆 [1,6] 和 [6,8]），判断条件稍有不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findMinArrowShots(vector<vector<int>>& points) {
    // 按右端点排序
    sort(points.begin(), points.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    int arrows = 1;
    int last_r = points[0][1];  // 当前这支箭的位置（右端点）

    for (int i = 1; i < (int)points.size(); i++) {
        if (points[i][0] > last_r) {
            // 这个气球在当前箭射不到的地方，需要新箭
            arrows++;
            last_r = points[i][1];
        }
        // points[i][0] <= last_r，当前箭能引爆，不用新箭
    }

    return arrows;
}

和 LeetCode 435 的细微差别：

需要新箭/不重叠条件 端点相等时
LeetCode 435 intervals[i][0] >= last_r 端点相等算不重叠
LeetCode 452 points[i][0] > last_r 端点相等算重叠（同一支箭能射到）

执行过程：

1
2
3
4
5
6
7
8
9
输入（按右端点排序后）：[1,6] [2,8] [7,12] [10,16]

初始：arrows=1，last_r=6（第一支箭射 x=6）

i=1: [2,8]，2 <= 6，当前箭能射到 → 不用新箭
i=2: [7,12]，7 > 6，射不到 → arrows=2，last_r=12（第二支箭射 x=12）
i=3: [10,16]，10 <= 12，当前箭能射到 → 不用新箭

结果：2 支箭

复杂度：

  • 时间：O(n log n)
  • 空间：O(1)

容易踩的坑

1. 合并区间别漏掉最后一个

扫描结束时，最后一个「当前区间」还没被放入结果，一定要在循环结束后手动 push_back。

1
2
// 循环结束，最后一个区间还没存
res.push_back({cur_l, cur_r});  // 不能省

2. 合并时右端点要取 max

相交的两个区间合并，右端点取 max，不是直接覆盖。因为可能遇到「大区间包含小区间」的情况：

1
2
3
[1, 10] 和 [2, 5]
cur_r 已经是 10，如果直接用 5 覆盖就错了
→ cur_r = max(10, 5) = 10  ✓

3. 按右端点排序 vs 按左端点排序

两类问题分别对应不同的排序方式：

问题类型 排序依据 原因
合并区间 / 插入区间 左端点升序 从左到右处理，保证顺序
保留最多 / 最少箭数 右端点升序 贪心：右端点小的先选，给后面留更多空间

4. 端点相等的判断

  • LeetCode 56（合并）：l <= cur_r 时合并，端点相等算重叠
  • LeetCode 435（不重叠）：l >= last_r 时不重叠，端点相等可以相邻
  • LeetCode 452（射气球）：l > last_r 时才是新区间，端点相等一支箭能射到

三题的边界条件不一样，要仔细看题意。

总结

mindmap
  root((区间问题))
    核心思想
      按左端点排序
        合并/插入类问题
      按右端点排序
        保留最多不重叠
        最少箭数/组数
    经典题目
      LeetCode 56 合并区间
      LeetCode 57 插入区间
      LeetCode 435 无重叠区间
      LeetCode 452 最少箭数
    常见陷阱
      合并后漏掉最后区间
      右端点用max而非覆盖
      端点相等的边界

各题核心对比：

题目 排序方式 扫描逻辑 时间复杂度
56 合并区间 左端点升序 有重叠就合并，无重叠就保存 O(n log n)
57 插入区间 无需排序（已有序） 三段处理：左/重叠/右 O(n)
435 无重叠区间 右端点升序 不冲突就保留，冲突就跳过 O(n log n)
452 最少箭数 右端点升序 射不到才加新箭 O(n log n)

区间问题的魅力在于，看起来各不相同，但底层都是同一套思路。刷完这几道，之后再见到类似的题，基本上排一下序就能想清楚了。

推荐阅读：