题目链接 · 灵神原题解（署名来源）

方法一：排序

以示例 1 为例，我们有 $[1,3],[2,6],[8,10],[15,18]$ 这四个区间。

为方便合并，把区间按照左端点从小到大排序（示例 1 已经按照左端点排序了）。排序的理由会在下面的合并过程中说明。

排序后，我们就知道了第一个合并区间的左端点，即 $\mathit{\text{intervals}}[0][0]=1$。

第一个合并区间的右端点是多少？目前只知道其 $\ge \mathit{\text{intervals}}[0][1]=3$，但具体是多少现在还不确定，得向右遍历。

具体算法如下：

1. 把 $\mathit{\text{intervals}}[0]$ 加入答案。注意，答案的最后一个区间表示当前正在合并的区间。
2. 遍历到 $\mathit{\text{intervals}}[1]=[2,6]$，由于左端点 $2$ 不超过当前合并区间的右端点 $3$，可以合并。由于右端点 $6>3$，那么更新当前合并区间的右端点为 $6$。由于我们已经按照左端点排序，所以 $\mathit{\text{intervals}}[1]$ 的左端点 $2$ 必然大于等于合并区间的左端点，所以无需更新当前合并区间的左端点。
3. 遍历到 $\mathit{\text{intervals}}[2]=[8,10]$，由于左端点 $8$ 大于当前合并区间的右端点 $6$，无法合并（两个区间不相交）。再次利用区间按照左端点排序的性质，更后面的区间的左端点也大于 $6$，无法与当前合并区间相交，所以当前合并区间 $[1,6]$ 就固定下来了，把新的合并区间 $[8,10]$ 加入答案。
4. 遍历到 $\mathit{\text{intervals}}[3]=[15,18]$，由于左端点 $15$ 大于当前合并区间的右端点 $10$，无法合并（两个区间不相交），我们找到了一个新的合并区间 $[15,18]$ 加入答案。

上述算法同时说明，按照左端点排序后，合并的区间一定是 $\mathit{\text{intervals}}$ 中的连续子数组。

答疑

问：能不能按照右端点排序？

答：可以，但是需要倒着遍历 $\mathit{\text{intervals}}$ 数组。如果正着遍历，比如 $[1,2],[4,5],[1,6]$ 这三个区间，正确答案是合并成 $[1,6]$，但正着遍历到 $[4,5]$ 这个区间时，无法知道 $[4,5]$ 能否和 $[1,2]$ 彻底断开。但按左端点排序的话，我们就知道这是不会断开的，会和之前的区间合并在一起。

本题视频讲解，欢迎点赞关注~

写法一

Python 解法1

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p: p[0])  # 按照左端点从小到大排序

        ans = []
        for p in intervals:
            if ans and p[0] <= ans[-1][1]:  # 左端点在合并区间内，可以合并
                ans[-1][1] = max(ans[-1][1], p[1])  # 更新合并区间的右端点
            else:  # 不相交，无法合并
                ans.append(p)  # 新的合并区间
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        ranges::sort(intervals); // 按照左端点从小到大排序

        vector<vector<int>> ans;
        for (auto& p : intervals) {
            if (!ans.empty() && p[0] <= ans.back()[1]) { // 左端点在合并区间内，可以合并
                ans.back()[1] = max(ans.back()[1], p[1]); // 更新合并区间的右端点
            } else { // 不相交，无法合并
                ans.emplace_back(p); // 新的合并区间
            }
        }
        return ans;
    }
};

写法二

直接生成合并后的区间，不修改 $\mathit{\text{ans}}$ 中的区间。

Python 解法3

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p: p[0])  # 按照左端点从小到大排序

        n = len(intervals)
        ans = []
        left, right = inf, -inf

        for i, (l, r) in enumerate(intervals):
            left = min(left, l)
            right = max(right, r)
            # 下一个区间与 [left, right] 不相交
            if i == n - 1 or intervals[i + 1][0] > right:  
                ans.append([left, right])
                left = inf

        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        ranges::sort(intervals, {}, [](auto& a) { return a[0]; }); // 按照左端点从小到大排序（另一种写法）

        int n = intervals.size();
        vector<vector<int>> ans;
        int left = INT_MAX, right = INT_MIN;

        for (int i = 0; i < n; i++) {
            left = min(left, intervals[i][0]);
            right = max(right, intervals[i][1]);
            // 下一个区间与 [left, right] 不相交
            if (i == n - 1 || intervals[i + 1][0] > right) {
                ans.push_back({left, right});
                left = INT_MAX;
            }
        }

        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\mathit{\text{intervals}}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。排序的栈开销和返回值不计入。

方法二：差分数组

创建一个计数数组 $\mathit{\text{cnt}}$，初始值均为 $0$。

对于区间 $[\mathit{\text{start}},\mathit{\text{end}}]$，把 $\mathit{\text{cnt}}[\mathit{\text{start}}],\mathit{\text{cnt}}[\mathit{\text{start}}+1],\dots ,\mathit{\text{cnt}}[\mathit{\text{end}}]$ 都增加 $1$。最终满足 $\mathit{\text{cnt}}[i]>0$ 的连续下标，就是合并后的区间。例如 $\mathit{\text{intervals}}=[[0,2],[1,3],[5,6]]$，对应的 $\mathit{\text{cnt}}=[1,2,2,1,0,1,1]$，其中下标 $i=0,1,2,3,5,6$ 的 $\mathit{\text{cnt}}[i]>0$，所以合并后的区间为 $[0,3]$ 和 $[5,6]$。

然而，这个做法有一个 bug，例如 $\mathit{\text{intervals}}=[[1,2],[3,4]]$，这两个区间不能合并，但按照上述做法，由于 $\mathit{\text{cnt}}=[0,1,1,1,1]$，我们会误认为合并后的区间为 $[1,4]$。

解决办法：把区间左右端点乘以 $2$，例如 $[1,2],[3,4]$ 变成 $[2,4],[6,8]$，这样就把相邻的区间用整数 $5$ 隔开了。对应的 $\mathit{\text{cnt}}=[0,0,1,1,1,0,1,1,1]$，区间为 $[2,4],[6,8]$。最后再把左右端点除以 $2$，得到 $[1,2],[3,4]$。

如何快速实现区间加一？请看 差分数组原理讲解。

Python 解法5

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        mx = max(p[1] for p in intervals)

        diff = [0] * (mx * 2 + 2)
        for start, end in intervals:
            # 把区间 [start*2, end*2] 增加 1
            diff[start * 2] += 1
            diff[end * 2 + 1] -= 1

        ans = []
        sum_d = 0
        start = -1  # -1 表示尚未遇到合并后的区间左端点
        for i, d in enumerate(diff):
            sum_d += d  # 计算 diff 的前缀和
            if sum_d > 0:
                if start < 0:
                    start = i  # 合并后的区间左端点
            elif start >= 0:
                # i-1 是合并后的区间右端点
                # 由于乘 2 操作，区间左右端点都是偶数，所以 i-1 是偶数，i 是奇数，(i-1)/2 == floor(i/2)
                ans.append([start // 2, i // 2])
                start = -1
        # 注：最后一轮循环 sum_d == 0，我们不会漏掉最后一个区间
        return ans

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int mx = 0;
        for (auto& p : intervals) {
            mx = max(mx, p[1]);
        }

        vector<int> diff(mx * 2 + 2);
        for (auto& p : intervals) {
            // 把区间 [p[0]*2, p[1]*2] 增加 1
            diff[p[0] * 2]++;
            diff[p[1] * 2 + 1]--;
        }

        vector<vector<int>> ans;
        int sum_d = 0;
        int start = -1; // -1 表示尚未遇到合并后的区间左端点
        for (int i = 0; i < diff.size(); i++) {
            sum_d += diff[i]; // 计算 diff 的前缀和
            if (sum_d > 0) {
                if (start < 0) {
                    start = i; // 合并后的区间左端点
                }
            } else if (start >= 0) {
                // i-1 是合并后的区间右端点
                // 由于乘 2 操作，区间左右端点都是偶数，所以 i-1 是偶数，i 是奇数，(i-1)/2 == floor(i/2)
                ans.push_back({start / 2, i / 2});
                start = -1;
            }
        }
        // 注：最后一轮循环 sum_d == 0，我们不会漏掉最后一个区间
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n+U)$，其中 $n$ 是 $\mathit{\text{intervals}}$ 的长度，$U=max({\mathit{\text{end}}}_i)$。
• 空间复杂度：$\mathcal{O}(U)$。返回值不计入。

方法三：扫描线

想象一根垂线从左到右，缓缓扫过每个区间。在这个过程中，用一个计数器 $\mathit{\text{cnt}}$ 表示当前垂线与多少个区间相交。

• 如果垂线遇到区间左端点 $\mathit{\text{start}}$，则垂线开始与该区间相交，把 $\mathit{\text{cnt}}$ 加一。如果加一前 $\mathit{\text{cnt}}=0$，则说明我们开始了一段新的合并区间，$\mathit{\text{start}}$ 是合并后的区间左端点。
• 如果垂线遇到区间右端点 $\mathit{\text{end}}$，则垂线结束与该区间相交，把 $\mathit{\text{cnt}}$ 减一。如果减一后 $\mathit{\text{cnt}}=0$，则说明 $\mathit{\text{end}}$ 是合并后的区间右端点。

区间 $[1,3]$ 和 $[2,6]$ 的合并过程如下：

1. 初始化 $\mathit{\text{cnt}}=0$。
2. 扫描线遇到左端点 $1$，现在 $\mathit{\text{cnt}}=1$。由于 $\mathit{\text{cnt}}$ 增加之前是 $0$，记录合并区间的左端点为 $1$。
3. 扫描线遇到左端点 $2$，现在 $\mathit{\text{cnt}}=2$。
4. 扫描线遇到右端点 $3$，现在 $\mathit{\text{cnt}}=1$。这说明我们仍然在一个区间内，合并过程没有结束。
5. 扫描线遇到右端点 $6$，现在 $\mathit{\text{cnt}}=0$。合并结束，把区间 $[1,6]$ 加入答案。

顺带一提，回顾方法二中的例子，对于 $[1,2],[3,4]$ 这样的区间，我们会在 $2$ 这个位置就判断出 $[1,2]$ 是个独立的区间，不会把 $[1,2]$ 和 $[3,4]$ 合并。

Python 解法7

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        events = defaultdict(int)
        for start, end in intervals:
            events[start] += 1  # 垂线遇到左端点则加一
            events[end] -= 1  # 垂线遇到右端点则减一
            # 这样处理后，就可以把 cnt 的更新逻辑统一成 cnt += events[x]，无需区分左右端点

        ans = []
        cnt = 0
        for x, c in sorted(events.items()):
            if cnt == 0:  # 扫描线开始与区间相交
                start = x  # x 是合并后的区间左端点
            cnt += c
            if cnt == 0:  # 扫描线结束与区间相交
                ans.append([start, x])  # x 是合并后的区间右端点
        return ans

C++ 解法7

// C++ 版待补充

C++ 解法8

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        map<int, int> events;
        for (auto& p : intervals) {
            events[p[0]]++; // 垂线遇到左端点则加一
            events[p[1]]--; // 垂线遇到右端点则减一
            // 这样处理后，就可以把 cnt 的更新逻辑统一成 cnt += events[x]，无需区分左右端点
        }

        vector<vector<int>> ans;
        int cnt = 0;
        int start;
        for (auto& [x, c] : events) {
            if (cnt == 0) { // 扫描线开始与区间相交
                start = x; // x 是合并后的区间左端点
            }
            cnt += c;
            if (cnt == 0) { // 扫描线结束与区间相交
                ans.push_back({start, x}); // x 是合并后的区间右端点
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\mathit{\text{intervals}}$ 的长度。瓶颈在排序（或者维护有序集合）上。
• 空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府