LeetCode算法题-合并区间

题目描述： 给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路分析：

  1. 对给出的二维数组进行排序，使得满足每一组第一个元素都小于等于后面一组第一个元素，例如这种形式：[[1,3],[2,6],[8,10]]。 [[1,3],[8,10],[2,6]]这种形式则需要调整。
  2. 贪心给出一个新的结果二维数组，每次去和已知数组比较，发生重合则重组后加入结果数组，否则则将已知数组的拷贝过来。

代码如下：

public static int[][] merge(int[][] intervals) {
        if (intervals.length==0) return new int[][]{};
        if (intervals.length ==1) return intervals;
        //处理输入，使得每一个里面的第一个元素递增
        for (int i=0; i<intervals.length-1; i++){
            for (int j=0; j<intervals.length-1-i; j++){
                if (intervals[j][0] > intervals[j+1][0]){
                    int[] tmp = intervals[j];
                    intervals[j] = intervals[j+1];
                    intervals[j+1] = tmp;
                }
            }
        }
        int[][] out = new int[intervals.length][2];
        out[0] = intervals[0];
        int count1 = 0;
        for (int i=1; i<intervals.length; i++){
            if (out[count1][1] < intervals[i][0]) out[++count1]=intervals[i];
            else out[count1] = new int[]{out[count1][0], Math.max(intervals[i][1],out[count1][1])};
        }
        return Arrays.copyOfRange(out,0,count1+1);

    }

总结

这种方法第2步不花时间，重点是第一步的冒泡排序时间太多了。这一题是中等难度题目，难度还是有的。

执行结果：
通过
显示详情
执行用时 :205 ms, 在所有 Java 提交中击败了7.40% 的用户
内存消耗 :51.4 MB, 在所有 Java 提交中击败了12.37%的用户