给出一个区间的集合，请合并所有重叠的区间。

示例 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] 可被视为重叠区间。

思路与代码

排序+顺序合并

1 首先根据二维数组的第一位从小到大进行排序，时间复杂度O(nlog(n)) 2 按顺序依次合并，需比较两个数组的左右边界确定是合并还是丢弃还是直接放入。

class Solution { public int[][] merge(int[][] intervals) { if (intervals.length == 0) return new int[0][0]; Arrays.sort(intervals, new Comparator<int[]>(){ @Override public int compare(int[] a, int[] b){ return a[0] - b[0]; } }); // Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]); List<int[]> list = new ArrayList(); for (int[] arr: intervals){ if (list.size() == 0 || list.get(list.size() - 1)[1] < arr[0]){ list.add(arr); }else if (arr[0] <= list.get(list.size()-1)[1] && arr[1] > list.get(list.size()-1)[1]){ list.get(list.size() - 1)[1] = arr[1]; } } return list.toArray(new int[list.size()][]); } }