LeetCode -- 合并区间

LeetCode链接：https://leetcode-cn.com/problems/merge-intervals/

题目：

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

示例：

　　输入：[[1, 3], [2, 6], [8, 10], [15, 18]]

　　输出：[[1, 6], [8, 10], [15, 18]]

　　输入：[[1, 4], [4, 5]]

　　输出：[[1, 5]]

　　解题思路：先将给定的区间按照左边界的大小进行排序，则排序后两个区间是否可以合并取决于，第一个区间的右边界>=第二个区间的左边界是否成立，如果成立则可以合并，如果不成立则不可以合并；

 1 import java.util.Comparator;
 2 import java.util.Arrays;
 3 
 4 public class Solution {
 5     public int[][] merge(int[][] intervals) {
 6         if(intervals == null || intervals.length == 0 || intervals[0].length == 0) return new int[0][0];
 7 
 8         Arrays.sort(intervals, new Comparator<int[]>() {       // 根据给定区间的左边界的大小进行排序
 9             public int compare(int[] o1, int[] o2) {
10                 return o1[0] - o2[0];
11             }
12         });
13         List<int[]> ans = new ArrayList();
14         int i = 0;
15         while(i < intervals.length) {           // 扫描排序后的区间，并进行合并
16             int left = intervals[i][0];
17             int right = intervals[i][1];
18             int j = i + 1;
19             for(; j < intervals.length; j++) {
20                 if(right >= intervals[j][0]) {
21                     right = Math.max(intervals[j][1], right);
22                 }else {
23                     break;
24                 }
25             }
26             ans.add(new int[] {left, right});
27             i = j;
28         }
29         int[][] res = new int[ans.size()][2];
30         int count = 0;
31         for(int[] cur : ans) {
32             res[count++] = cur;
33         }
34         return res;
35     }
36 }

　　时间复杂度：排序的时间复杂度为O(NlogN)，合并区间时只需要扫描一次数组，所以时间复杂度为O(N)，其中N为intervals.length;

　　空间复杂度：使用一个List存放合并后的结果，所以空间复杂度为O(N)，其中N为intervals的元素个数