分析

• 本题的考点：排序。

• 对于区间的题目，一般来说，都会涉及到排序，可能按照左端点排序，也可能按照右端点排序。

• 本题分为两步：

（1）按照左端点升序排序；

（2）初始让区间[l, r]，其中l=a[0][0], r=a[0][1]，从第2个区间开始，从左向右依次遍历每个区间，如果该区间与区间[l, r]有交集，则更新区间右端点r；否则我们得到一个没有交集的新区间，并更新区间[l, r]，继续考虑下一个区间。

代码

• C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {

        sort(a.begin(), a.end());

        vector<vector<int>> res;
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < a.size(); i++) {
            if (a[i][0] > r) {  // 区间无交集
                res.push_back({l, r});
                l = a[i][0], r = a[i][1];
            } else r = max(r, a[i][1]);  // 区间有交集, 需要合并
        }
        res.push_back({l, r});  // 最后一个合并后的区间

        return res;
    }
};

• Java

class Solution {
    public int[][] merge(int[][] a) {

        Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> res = new ArrayList<>();
        int l = a[0][0], r=  a[0][1];
        for (int i = 1; i < a.length; i++) {
            if (a[i][0] > r) {
                res.add(new int[]{l, r});
                l = a[i][0]; r = a[i][1];
            } else r = Math.max(r, a[i][1]);
        }
        res.add(new int[]{l, r});

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

时空复杂度分析

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

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