合并区间 图解题解

这道题到底在问什么

输入

[[1,3],[2,6],[8,10],[15,18]]

输出

[[1,6],[8,10],[15,18]]

最优解：一步一步想明白

1. 3区间顺序乱时两两比，不光 O(n²) 慢，还容易漏掉「A 和 B 合并后，合出来的大区间又跟 C 重叠」这种连环情况，逻辑很绕。
2. 4转折：排序后，能重叠的区间必然相邻。证明很直观——若 A 起点 ≤ B 起点、A 和 C 重叠，那起点夹在中间的 B 一定也跟 A 沾边。于是只需从左到右扫一遍，拿当前区间跟「结果里最后一段 merged」比就够了：当前起点 ≤ merged 的终点就合并（终点取更大的），否则新开一段。一遍 O(n) 搞定，再不用两两回头比。
3. 5merged = 空本例输入起点恰好递增，排序后顺序不变：1、2、8、15。结果列表 merged 现在是空的。
4. 6merged = [[1,3]]第一个 [1,3] 没东西可比，直接放进结果。当前合并段 [s,e] = [1,3]。
5. 7起点 2 ≤ 终点 3[2,6] 的起点 2 没超过末段 [1,3] 的终点 3 → 重叠。该合并，而不是新开。
6. 8merged = [[1,6]]合并时终点取更大的：max(3, 6)=6，末段被拉长成 [1,6]。注意起点 1 不变，只把终点往右拉。
7. 9起点 8 ＞ 终点 6负例分支来了：[8,10] 的起点 8 已经超过末段 [1,6] 的终点 6，接不上 → 不合并，把 [8,10] 当新的一段 append 进结果。
8. 10merged = [[1,6],[8,10]]现在结果末段换成了 [8,10]，接下来的区间只需要跟它比。前面合好的 [1,6] 已经定型，不再回头看。
9. 11起点 15 vs 终点 10轮到最后一个 [15,18]。还是老规矩：拿它的起点 15，跟结果末段 [8,10] 的终点 10 比一比。
10. 12起点 15 ＞ 终点 10[15,18] 的起点 15 又超过末段 [8,10] 的终点 10，同样接不上，再新开一段。扫完，结果 = [[1,6],[8,10],[15,18]]，三段互不重叠。
11. 15区间题的万能第一步——按端点排序。排完之后，绝大多数区间问题都能一遍扫描搞定，每个新区间只跟「结果里最后一段」打交道。
12. 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def merge(self, intervals):
        intervals.sort()
        ans = []
        for start, end in intervals:
            if not ans or start > ans[-1][1]:
                ans.append([start, end])
            else:
                ans[-1][1] = max(ans[-1][1], end)
        return ans

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;
        for (auto& iv : intervals) {
            if (ans.empty() || iv[0] > ans.back()[1]) ans.push_back(iv);
            else ans.back()[1] = max(ans.back()[1], iv[1]);
        }
        return ans;
    }
};

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        for (int[] iv : intervals) {
            if (ans.isEmpty() || iv[0] > ans.get(ans.size()-1)[1]) ans.add(iv);
            else ans.get(ans.size()-1)[1] = Math.max(ans.get(ans.size()-1)[1], iv[1]);
        }
        return ans.toArray(new int[0][]);
    }
}

# 区间合并 骨架
intervals.sort(key=lambda x: x[0])    # 按起点排序
merged = []
for s_, e_ in intervals:
    if merged and s_ <= merged[-1][1]:      # 起点 ≤ 末段终点 → 重叠
        merged[-1][1] = max(merged[-1][1], e_)   # 拉长末段终点
    else:
        merged.append([s_, e_])             # 否则新开一段
return merged

复杂度

面试官可能追问