合并区间 图解题解

合并区间这道题在问什么

给一堆可能互相重叠的区间 [start, end]，要求把所有叠在一起的区间合并成一段，输出一组互不重叠、又恰好覆盖全部输入的区间。比如 [[1,3],[2,4],[6,8]]，前两个叠着，合成 [1,4]，答案是 [[1,4],[6,8]]。难点不在「怎么合两个区间」，而在乱序输入下怎么知道谁和谁该合——这决定了第一步必须是排序。

为什么合并区间必须先按起点排序

如果不排序，直接从左往右扫，你没法只和「上一段」比：后面随时可能冒出一个起点更小的区间，回头和早已处理过的段重叠，一趟扫描就失效了，只能退化成两两比较。

按起点从小到大排序后，起点单调不减，一个新区间要么接在最近合并出的那段上（重叠或相接），要么整体落在它右边。它绝不可能越过最近一段去和更早的段重叠——因为更早的段已经被最近一段「吞并或隔开」了。于是每个区间只需做一次比较，线性一趟就够。

怎么判断两个区间重叠，等号算不算

扫描时手里始终握着一个「当前合并段」，只关心它的右端 curE。新区间 [s, e] 来了就比一次：s ≤ curE 说明新区间的头没越过当前段的尾，两段叠着或端点相接，并进去；s > curE 说明中间断开了，旧段定型收进结果，用 [s, e] 另起一段。

等号必须算重叠：[1,3] 和 [3,5] 在 3 处相接，按题意要合成 [1,5]，判断写成 s < curE 就会把它们错误拆开。另一个细节是合并时右端要取 max(curE, e) 而不是直接赋成 e——新区间可能被当前段完全包住，比如当前段是 [1,9]、来了个 [2,5]，直接赋值会把右端从 9 改小成 5。

为什么当前段的起点永远不用更新

因为区间已按起点排序，当前段的起点是这一片区间里最小的起点；之后并进来的区间起点只会更大，不可能把段的左边界往左推。所以合并动作只有一个方向：右端往大里拉。这也解释了为什么整个算法状态可以精简到只记 res 里最后一段——参考代码里 res[-1][1] = max(res[-1][1], e) 一行就是全部合并逻辑。

复杂度怎么算，有哪些边界

时间 O(n log n)：瓶颈在排序，排好后线性扫一遍只花 O(n)。空间 O(n)：结果数组最坏放下全部 n 个区间（两两不重叠时原样输出）；反过来最好情形所有区间连成一片，结果只剩 1 个。

最容易翻车的三处：忘记排序直接扫、漏掉端点相等的重叠、合并时不取 max 导致右端被改小。写完拿一组含「完全包含」和「端点相接」的用例各验一遍，基本就稳了。

Python

def merge(intervals):
    intervals.sort(key=lambda x: x[0])   # 按起点排序
    res = []
    for s, e in intervals:
        if res and s <= res[-1][1]:      # 与上一段重叠
            res[-1][1] = max(res[-1][1], e)
        else:                            # 断开，另起一段
            res.append([s, e])
    return res

C++

vector<vector<int>> merge(vector<vector<int>>& a){
    sort(a.begin(), a.end());
    vector<vector<int>> res;
    for (auto& it : a) {
        if (!res.empty() && it[0] <= res.back()[1])
            res.back()[1] = max(res.back()[1], it[1]);
        else res.push_back(it);
    }
    return res;
}

Java

public int[][] merge(int[][] a) {
    Arrays.sort(a, (x, y) -> x[0] - y[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] it : a) {
        int n = res.size();
        if (n > 0 && it[0] <= res.get(n-1)[1])
            res.get(n-1)[1] = Math.max(res.get(n-1)[1], it[1]);
        else res.add(it);
    }
    return res.toArray(new int[0][]);
}