以數組 intervals 表示若干個區間的集合，其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間，并返回 一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間 。

示例 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 <= intervals.length <= $10^4$
intervals[i].length == 2
0 <= starti <= endi <= $10^4$

---

知識點：
數組、排序

---

解：
因為需要合并若干個區間，因此對左端點進行升序排序，使用到lambda表達式。

對于每個區間，左端點表示這個區間的起始下標，右端點表示這個區間的結束下標。

定義一個列表，存儲結果，列表的每個元素都是一個int類型的一維數組。

對于intervals的每個元素（即：每一行），按照以下步驟進行：
①獲取當前結果列表res的大小
②若當前結果列表res沒有元素，表示我們直接原始數組的第一行加入這個結果列表res
③若當前結果列表res有元素，且最后一個元素的右端點≥當前遍歷的元素的左端點，如：[1, 3]與[2, 5]，表明需要合并區間。因為這個區間已經在結果列表res中，我們做的就是替換這個區間在res的相應左端點：獲取更大的結束下標。對于這個例子而言，最大的結束下標是5，也就是p[1]，因此讓結果列表res中的最后一個元素的右端點更新為這個5。若[1, 4]與[2, 3]，則最大的結束下標是4，也就是res.get(len-1)[1]，因此結果列表res中的最后一個元素的右端點更新為這個4。
④若當前結果列表res有元素，但最后一個元素的右端點＜當前遍歷的元素的左端點，則表明無法與當前正在處理的結果列表中的最后一個區間進行合并，那就往res新增一個元素。

最后，我們將List列表，通過.toArray()轉為數組，返回。

時間復雜度：$O(nlogn)$。Arrays.sort()平均耗時$O(nlogn)$
空間復雜度：$O(1)$。排序的棧開銷和返回值不計入

class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new ArrayList<>(); //最后一個元素表示正在合并的區間//原始數據按第一列進行排序Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));//遍歷每一行for (int[] p : intervals) {//獲取當前結果列表的大小int len = res.size();//若結果列表有元素，且可合并if (len > 0 && res.get(len - 1)[1] >= p[0]) {//更新右端點最大值res.get(len - 1)[1] = Math.max(res.get(len - 1)[1], p[1]);}//無法合并else {//添加新的合并區間res.add(p);}}//列表轉數組并返回return res.toArray(new int[res.size()][]);}
}

---

參考：
1、靈神解析
2、java二維數組排序