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

示例 1：

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

示例 2：

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

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

思路

首先把数组的开区间数值按照生序的方式排序，生成排序后的数据。使用当前数据的闭区间和下个数组的开区间进行比较。如果闭区间大于开区间说明下个数组也在当前区间内，闭区间小于开区间说明下个数组是在当前区间以外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[][] merge(int[][] intervals) {

        // 按照[0]排序合并后的区间一定是连续
        Arrays.sort(intervals, Comparator.comparingInt(x ->x[0]));
        // 存放区间数据
        List<int[]> temList = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            // 取左区间, 右区间
            int l = intervals[i][0], r = intervals[i][1];
            // 初始化的时候, 取集合中最后一个闭区间和下一个开区间进行比较, 大于说明是新的区间,小于把下个闭区间更新当前区间
            if (temList.isEmpty() || temList.get(temList.size() - 1)[1] < l){
                temList.add(new int[]{l,r});
            } else {
                temList.get(temList.size() - 1)[1] = Math.max(temList.get(temList.size() - 1)[1], r);
            }
        }
        return temList.toArray(new int[temList.size()][]);
    }
}

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/array-and-string/c5tv3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。