56.合并區(qū)間

排序：
如果按照區(qū)間的左端點(diǎn)排序，那么在排完序的列表中，可以合并的區(qū)間一定是連續(xù)的，如下圖所示，標(biāo)記為藍(lán)色、黃色和綠色的區(qū)間分別可以合并為一個(gè)大區(qū)間，它們?cè)谂磐晷虻牧斜碇惺沁B續(xù)的

算法：

使用數(shù)組merged存儲(chǔ)最終的答案

首先，將列表中的區(qū)間按照左端點(diǎn)升序排序，然后我們將第一個(gè)區(qū)間加入merged數(shù)組中，并按順序依次考慮之后的每個(gè)區(qū)間：

• 如果當(dāng)前區(qū)間的左端點(diǎn)在數(shù)組merged中最后一個(gè)區(qū)間的右端點(diǎn)之后，那么它們不會(huì)重合，我們可以直接將這個(gè)區(qū)間加入數(shù)組merged的末尾
• 否則，它們重合，需要用當(dāng)前區(qū)間的右端點(diǎn)更新數(shù)組merged中最后一個(gè)區(qū)間的右端點(diǎn)，將其設(shè)置二者的較大值

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()][]);}
}