yicong@algo: ~/code/05-array/0056-merge-intervals.cpp

yicong@algo:~/code/05-array$ cat 0056-merge-intervals.cpp

56. 合并区间

中等 普通数组 题目 ↗ 源码 ↗

// 思路

两个区间 [a1, a2] 和 [b1, b2](a1 <= b1)能合并的条件是 a2 >= b1, 合并结果是 [a1, max(a2, b2)]。 但如果不排序,任意两个区间都可能重叠,得两两比较,O(n²)。 关键观察:先按左端点排序,那么可能重叠的区间在排序后一定是相邻的 (或者隔着几段已经被前一步合并掉的区间)。于是只需要一趟线性扫描: 从左往右走,维护"当前正在合并的那一段"的右端点 lastEnd: - 如果下一个区间的左端点 <= lastEnd,说明重叠,把它并进来, 右端点更新为 max(lastEnd, 新区间右端点); - 否则不重叠,把当前段收进答案,从新区间重新开一段。 版本一:排序 + 额外结果数组,最直观。 版本二:原地合并,把答案写回原数组再用 resize 截断, 省掉一份 O(n) 的额外结果数组(排序本身还是 O(log n) 栈空间)。

// 时间复杂度

O(n log n),瓶颈在排序;合并那一趟是 O(n)。

// 空间复杂度

版本一:O(n),额外存放结果 版本二:O(1)(不计排序的递归栈和返回值的拷贝),直接在原数组上就地压缩 注意:返回值按值拷贝一份,那部分空间是题目接口决定的,不算算法额外空间。

// 易错点

1. 必须按左端点排序。按右端点排,或者不排,都不对。 2. 判重叠是 <=,不是 <。比如 [1,4] 和 [4,5] 要合并成 [1,5], 写成 lastEnd < intervals[i][0] 会把它俩拆开。 3. 合并时右端点要取 max,不能直接赋值 intervals[i][1]。 反例:[1,10] 和 [2,3],后者的右端点更小,直接赋值会得到 [1,3]。 4. sort 的比较函数参数用 const vector<int>&,不要按值传,否则每次都拷贝。 5. 版本二里合并时用的是 intervals[write-1][1](已经合并过的值), 不能写成 intervals[i-1][1](那是原始的、还没合并的值)。 6. 空输入要能返回空数组;单个区间应原样返回。

// 面试口述要点

1. 先说不排序的两两比较是 O(n²),再说排序后只需一趟扫描; 2. 讲清"排序后可能重叠的区间一定相邻"这个观察,这是 O(n log n) 的根据; 3. 讲清合并条件 a2 >= b1 和右端点取 max 的原因(存在被完全包含的区间); 4. 如果被追问空间,可以给原地版本:答案写回原数组,最后 resize 截断; 5. 顺带提一句:intervals 的元素是 vector<int>,默认的 sort 就是按字典序比, 等价于按左端点排,所以这道题连比较函数都可以不写。但显式写出来更清楚。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // ================================================================
    // 版本一:排序 + 额外结果数组
    //   按左端点排序后,从左到右一趟扫描,边扫边合并
    // ================================================================
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = (int)intervals.size();
        if (n == 0) {
            return {};
        }

        // 按左端点升序排序
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] < b[0];
             });

        vector<vector<int>> ans;

        for (int i = 0; i < n; i++) {
            if (ans.empty() || ans.back()[1] < intervals[i][0]) {
                // 不重叠:把它作为一个新的段放进去
                ans.push_back(intervals[i]);
            } else {
                // 重叠:把右端点扩展到两者的较大值
                // 必须取 max,因为可能是 [1,10] 和 [2,3] 这种被完全包含的情况
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            }
        }

        return ans;
    }

    // ================================================================
    // 版本二:原地合并,省掉结果数组
    //   用 write 指向"下一个要写入的位置",答案直接在 intervals 的前 write 个位置里
    //   结束时 resize(write) 把尾巴截掉
    //   注意:这个函数会修改 intervals
    // ================================================================
    vector<vector<int>> merge_v2(vector<vector<int>>& intervals) {
        int n = (int)intervals.size();
        if (n == 0) {
            return {};
        }

        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] < b[0];
             });

        int write = 0;                               // 下一个要写入的位置

        for (int i = 0; i < n; i++) {
            // write == 0 表示还没有任何一段,先放一段进去
            // intervals[write - 1][1] 是"当前正在合并的那一段"的右端点
            if (write == 0 || intervals[write - 1][1] < intervals[i][0]) {
                intervals[write] = intervals[i];     // 不重叠,开新段
                write++;
            } else {
                // 重叠,扩展当前段的右端点
                intervals[write - 1][1] = max(intervals[write - 1][1], intervals[i][1]);
            }
        }

        intervals.resize(write);
        return intervals;
    }
};

// 本地测试:输入 n,然后 n 对整数(每对是一个区间);每行输出合并后的一个区间
// 同时跑两个版本并比对结果,版本二会改数组所以各用一份副本
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> intervals(n, vector<int>(2));
    for (int i = 0; i < n; ++i)
        cin >> intervals[i][0] >> intervals[i][1];

    vector<vector<int>> copy = intervals;            // 给版本二留一份
    vector<vector<int>> ans1 = Solution().merge(intervals);
    vector<vector<int>> ans2 = Solution().merge_v2(copy);

    if (ans1 != ans2) {
        cout << "MISMATCH\n";
        cout << "v1:";
        for (const vector<int>& v : ans1) cout << " [" << v[0] << "," << v[1] << "]";
        cout << "\nv2:";
        for (const vector<int>& v : ans2) cout << " [" << v[0] << "," << v[1] << "]";
        cout << '\n';
        return 0;
    }

    if (ans1.empty()) {
        cout << "none\n";
    } else {
        for (const vector<int>& v : ans1)
            cout << v[0] << ' ' << v[1] << '\n';
    }
    return 0;
}