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

數據結構

二維鏈表存儲每個區間

方法

先對每個區間的左邊界大小排序，（從左到右，依次比較a鏈表的右區間 和 其他鏈表的左區間）
判斷每個鏈表的左右邊界大小，
函數：a鏈表的右區間大于b鏈表的左區間，可以合并出：a鏈表的左區間，b鏈表的右區間。

我們用數組 merged 存儲最終的答案。
首先，我們將列表中的區間按照左端點升序排序。然后我們將第一個區間加入 merged 數組中，并按順序依次考慮之后的每個區間：
如果當前區間的左端點在數組 merged 中最后一個區間的右端點之后，那么它們不會重合，我們可以直接將這個區間加入數組 merged 的末尾；
否則，它們重合，我們需要用當前區間的右端點更新數組 merged 中最后一個區間的右端點，將其置為二者的較大值。

代碼java

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0){return new int[0][2];}Arrays.sort(intervals,new Comparator<int[]>(){public int compare(int[] interval1,int[] interval2){return interval1[0]-interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for(int i=0;i<intervals.length;++i){int L = intervals[i][0],R = intervals[i][1];if(merged.size()==0 || merged.get(merged.size()-1)[1]<L){merged.add(new int[]{L,R});} else{merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1],R);}}return merged.toArray(new int[merged.size()][]);}
}

代碼python

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x:x[0])merged = []for interval in intervals:if not merged or merged[-1][1]<interval[0]:merged.append(interval)else:merged[-1][1] = max(merged[-1][1],interval[1])return merged