一、题目

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

点击查看原题
难度级别： 中等

二、思路

1）排序

将每个区间的左边对齐，找到最大的右侧。

三、代码

1）排序

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         Arrays.sort(intervals, (int[] a, int[] b) -> {
  4.             return a[0] - b[0];
  5.         });
  6.         List<int[]> ans = new ArrayList();
  7.         int loc = 0;
  8.         while (loc < intervals.length) {
  9.             int left = intervals[loc][0];
  10.             int right = intervals[loc][1];
  11.             loc++;
  12.             while (loc < intervals.length) {
  13.                 if (right < intervals[loc][0]) {    // 当前区间没有覆盖的区间，就跳过
  14.                     break;
  15.                 }
  16.                 right = Math.max(right, intervals[loc][1]);    // 覆盖当前loc所指区间，则找到最大右侧
  17.                 loc++;
  18.             }
  19.             ans.add(new int[]{left, right});
  20.         }
  21.         return ans.toArray(new int[ans.size()][2]);
  22.     }
  23. }

时间复杂度位O(nlogn)，排序需要用栈，空间复杂度位O(logn)