【LC100】No56. 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

 提示:

• 1 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= starti <= endi <= 104

示例

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

链接

思路

先考虑的是直接遍历，发现除了暴力法无法在更短的时间复杂度内处理合并，那肯定是我没想到。

由于题目只返回合并后的结果，所以原数组 intervals 的顺序不重要，因此我们可以先将 intervals 排序。

比较简单的思路是：根据左端点排序，之后挨个枚举合并。

此时可以保证遍历到 intervals[i] 时，更早之前的元素都已经合并处理过，无需再次判断。

解法一：排序

先排序，后遍历依次处理合并。

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }
        // 保存合并后的结果
        List<int[]> res = new ArrayList();
        // 按照左端点排序
        Arrays.sort(intervals, (p, q) -> p[0]-q[0]);
        for (int[] interval : intervals) {
            int len = res.size();
            // 例如[1,3]和[2,6]形式的两个区间可以合并
            if (len > 0 && interval[0] <= res.get(len - 1)[1]) {
                res.get(len - 1)[1] = Math.max(interval[1], res.get(len - 1)[1]);
            } else {
                res.add(interval);
            }
        }
        // 转成数组返回
        return res.toArray(new int[res.size()][]);
    }
}

• 时间复杂度：O(nlogn)

• 空间复杂度：O(n)