這道題我想了一會兒，實在想不到比較好的算法，只能硬著頭皮寫了，然后不斷的debug，經(jīng)過我不懈的努力，最后還是AC，不過效率確實低。

我就是按照最直接的方法來，先把intervals數(shù)組按照第一個數(shù)start來排序，這個是通過定義一個sort方法用冒泡排序?qū)崿F(xiàn)的，然后用一個List<int[]>來裝答案，先把intervals[0]放進(jìn)答案，用index表示list中最新放入的那個答案的索引(ans.get(index))，然后從i=1開始遍歷intervals[i]，因為我這個intervals是排過序的，所以后面的intervals[i]的start一定大于等于前面的intervals[i]的start，但是如果intervals[i][0]比最新放入答案的intervals[i][1](ans.get(index)[1])還小，說明intervals[i][0]應(yīng)該在剛放入的最新答案(ans.get(index))的區(qū)間之中，所以我們要去更改那個最新的答案(ans.get(index))的end，把ans.get(index)[1]改為當(dāng)前元素的end和他自己的end的最大值，這樣就可以確保區(qū)間無重疊且完整，以下是我的代碼：

class Solution {public int[][] merge(int[][] intervals) {int n = intervals.length;int index =-1;sort(intervals);List<int[]> ans = new ArrayList<int[]>();ans.add(intervals[0]);index++;for(int i=1;i<n;i++){if(intervals[i][0] <= ans.get(index)[1]){ans.get(index)[1] = Math.max(ans.get(index)[1],  intervals[i][1]);}else{ans.add(intervals[i]);index++;}}int size = ans.size();int[][] res = new int[size][2];for(int i=0;i<size;i++){res[i] = ans.get(i);}return res;}public void sort(int[][] intervals){int n = intervals.length;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(intervals[i][0] > intervals[j][0]){int[] tmp = new int[]{intervals[i][0], intervals[i][1]};intervals[i][0] =intervals[j][0];intervals[i][1] = intervals[j][1];intervals[j][0] = tmp[0];intervals[j][1]=tmp[1];}}}}
}

一看題解我都驚了，我去，和我的想法一摸一樣，我還以為我這種方法很low，原來這是官方解法，以下是題解代碼：

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

原理和我的算法是一模一樣的，不一樣的是他沒有自己定義排序方法而是用了Array.sort()方法，然后重寫compare()方法,比較數(shù)組中第一個元素也就是strat就可以，然后他也沒用index來記錄剛放進(jìn)去的最新答案，而是通過merged.get(merged.size()-1)來獲得這個剛放進(jìn)去的最新答案。