56. 合并区间

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

示例 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] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

intervals[i][0] <= intervals[i][1]

思路：排序 + 双指针

先将二维数组中的所有子区间按左边界从小到大排序。

然后遍历所有的子区间，维护两个数字，分别是当前合并区间的左边界和右边界，每次遍历时，判断当前合并的右边界是否小于下个小区间的左边界，如果小于的话，说明当前合并区间和下个小区间没有交集，将当前的左右边界作为一个区间的左右边界存入结果集中，并重置下个合并区间的左右边界为下个小区间的左右边界；如果当前合并区间的右边界大于等于下个小区间的左边界，说明当前合并区间和下个小区间有交集，把合并区间的右边界更新为 下个小区间的右边界和当前合并区间右边界中的较大值，从而让合并区间扩张。

最后还需要再将合并区间的左右边界添加到结果集中一次，因为循环中没有把最后一个合并区间添加到结果集中。

 1 class Solution {
 2     public int[][] merge(int[][] intervals) {
 3         if(intervals == null || intervals.length == 0){
 4             return new int[0][0];
 5         }
 6         // 将所有的区间按左区间大小从小到大排序
 7         Arrays.sort(intervals, new Comparator<int[]>(){
 8             public int compare(int[] a, int[] b){
 9                 return a[0] - b[0];
10             }
11         });
12         int leftBorder = intervals[0][0], rightBorder = intervals[0][1];
13         int len = intervals.length;
14         ArrayList<int[]> res = new ArrayList<>();
15         for(int i = 1; i < len; i++){
16             if(rightBorder < intervals[i][0]){  // 说明不可能和下个集合有交集
17                 //System.out.println(leftBorder + " " + rightBorder);
18                 res.add(new int[]{leftBorder, rightBorder});
19                 leftBorder = intervals[i][0];
20                 rightBorder = intervals[i][1];
21             }else{
22                 rightBorder = Math.max(rightBorder, intervals[i][1]);   // 说明有交集
23             }
24         }
25         res.add(new int[]{leftBorder, rightBorder});
26         return res.toArray(new int[res.size()][2]);
27     }
28 }

leetcode 执行用时：7 ms > 90.82%, 内存消耗：41 MB > 92.54%

复杂度分析：

时间复杂度：O(nlogn), n 为数组长度，时间花费主要分为两部分，一部分是排序，时间复杂度为O(nlogn), 接下来一次遍历的时间花费为O(n)。

空间复杂度：O(1), 如果不算上 res 这个结果列表的空间开销的话，那空间复杂度就是O(1)