LeetCode56.合并区间

这道题我想了一会儿，实在想不到比较好的算法，只能硬着头皮写了，然后不断的debug，经过我不懈的努力，最后还是AC，不过效率确实低。

我就是按照最直接的方法来，先把intervals数组按照第一个数start来排序，这个是通过定义一个sort方法用冒泡排序实现的，然后用一个List<int[]>来装答案，先把intervals[0]放进答案，用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]应该在刚放入的最新答案(ans.get(index))的区间之中，所以我们要去更改那个最新的答案(ans.get(index))的end，把ans.get(index)[1]改为当前元素的end和他自己的end的最大值，这样就可以确保区间无重叠且完整，以下是我的代码：

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()方法,比较数组中第一个元素也就是strat就可以，然后他也没用index来记录刚放进去的最新答案，而是通过merged.get(merged.size()-1)来获得这个刚放进去的最新答案。