关于leetcode第56题合并重复区间的解析

[toc]

1.题目描述

给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。

https://leetcode-cn.com/problems/merge-intervals/

2.解题思路

对于此题，考虑到区间的比较，那么最容易想到的就是将区间从小到大的顺序进行排序。滞后再两两比较就会容易很多，但是由于输入和输出都是二维数组，那么肯定需要一个额外的结果集来存储输出结果或者使用Arrays.copyOf方法。

2.1 使用排序

需要注意的是二维数组的排序方法，如果要使用Arrays.sort();则需要自己实现一个比较方法。之后将发生比较的结果存储在另外一个数组中。完整解析如下：

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(v1,v2)-> v1[0]-v2[0]);
        int res[][] = new int[intervals.length][2];
        int index = -1;
        for(int[] interval : intervals){
            if(index== -1 || interval[0] > res[index][1]){
                res[++index] = interval;
            }else {
                res[index][1] = Math.max(res[index][1],interval[1]);
            }
        }
        return Arrays.copyOf(res,index+1);
    }

在排序之后，申明了一个res数组来存储每次比较的结果，同时将使用index记录 res中添加元素的次数。最后采用Arrays.copyOf方法。
此算法由于开始进行了排序，后续又再次copy了结果，无论是时间还是空间都不是最优的算法。

image.png

2.1 不使用排序

如果不使用排序，那么用两次比较的话，只能将被合并进去的区间设置为null，之后再用另外一个数组将非空的元素copy出来。那么我们可以考虑双层for循环，由于外层的i只会进行一次比较，那么当出现合并情况之后，将i指向的元素设置为null，之后将j指向的元素合并，还可以再次进行比较。具体算法如下：

    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length <= 1){
            return intervals;
        }
        int count = 0;
        //循环比较，用i指向被合并的区间，j指向合并后的区间，入果存在合并，则i为null，并记录合并发生的次数count
        for(int i=0;i<intervals.length;i++){
            for(int j=i+1;j<intervals.length;j++){
                if(intervals[i][0]<=intervals[j][1]&&intervals[i][1]>=intervals[j][0]){
                    intervals[j][0] = Math.min(intervals[i][0],intervals[j][0]);
                    intervals[j][1] = Math.max(intervals[i][1],intervals[j][1]);
                    intervals[i] = null;
                    count ++;
                    break;
                }
            }
        }
        //复制结果集
        int index = 0;
        int[][] res = new int[intervals.length - count][2];
        for(int i=0;i<intervals.length;i++){
            if(intervals[i] != null){
                res[index][0] = intervals[i][0];
                res[index][1] = intervals[i][1];
                index++;
            }
        }
        return res;
    }

虽然代码量比第一种方法多了很多，但是时间和空间的效率要高很多。看来使用排序之后再合并并不是一个好办法。

image.png