排序：

用数组merged存储最终的答案

首先，将列表中的区间按照左端点升序排序，将第一个区间加入merged数组中，并按顺序依次考虑之后的每个区间：

• 如果当前区间的左端点在数组merged中最后一个区间的右端点之后，那么它们不会重合，可以将这个区间加入数组merged的末尾。
• 否则，它们重合，需要用当前区间的右端点更新数组merged中最后一个区间的右端点，将其置为二者的较大值。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] - o2[0];}});//System.out.println(Arrays.deepToString(intervals));List<int[]> list = new ArrayList<>();list.add(new int[]{intervals[0][0], intervals[0][1]});for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] > list.get(list.size() - 1)[1]) {list.add(new int[]{intervals[i][0], intervals[i][1]});} else {int[] last = list.get(list.size() - 1);last[1] = Math.max(last[1], intervals[i][1]);}}return list.toArray(new int[list.size()][]);}
}

复杂度分析：

• 时间复杂度：O(nlogn)，其中n为区间的数量。除去排序的开销，只需要依次线性扫描，所以主要的时间开销是排序的O(nlogn)。
• 空间复杂度：O(logn)，其中n为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn)即为排序所需要的空间复杂度。