分析

• 本题的考点：模拟。

• 可以把原来的区间分为三类：（1）左侧和待插入的区间没有交集的区间，（2）有交集的区间，（3）右侧和待插入的区间没有交集的区间。

• （1）直接放入结果数组中即可，合并（2），最后（3）直接放入结果数组中即可。

代码

• C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {

        vector<vector<int>> res;

        int k = 0;
        while (k < a.size() && a[k][1] < b[0]) res.push_back(a[k++]);  // 左侧无交集的部分

        if (k < a.size()) {
            b[0] = min(b[0], a[k][0]);
            while (k < a.size() && a[k][0] <= b[1]) b[1] = max(b[1], a[k++][1]);
        }
        res.push_back(b);

        while (k < a.size()) res.push_back(a[k++]);  // 右侧无交集的部分

        return res;
    }
};

• Java

class Solution {
    public int[][] insert(int[][] a, int[] b) {

        List<int[]> res = new ArrayList<>();

        int k = 0;
        while (k < a.length && a[k][1] < b[0]) res.add(a[k++]);  // 左侧无交集的部分

        if (k < a.length) {
            b[0] = Math.min(b[0], a[k][0]);
            while (k < a.length && a[k][0] <= b[1]) b[1] = Math.max(b[1], a[k++][1]);
        }
        res.add(b);

        while (k < a.length) res.add(a[k++]);  // 右侧无交集的部分

        return res.toArray(new int[0][0]);
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数组长度。

• 空间复杂度：$O(1)$。不考虑存储结果的数组。