Leetcode日记–56. Merge Intervals

发布于 2020-10-31  120 次阅读


碎碎念:今晚S10,SN十年老粉了,冲冲冲!

题目如下:

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Constraints:

intervals[i][0] <= intervals[i][1]

思路:

不知道为啥,我总觉得这道题写过,就是把二维数组使用一个comparator按照区间起始位置升序排序,然后比较相邻区间的值。若当前区间的第一个结束位置大于下一个区间的开始位置,则可以合并,取二者结束位置中的较大值作为合并后新区间的结束位置即可。

具体实现的时候有个骚方法,因为我们并不知道合并后的二维数组大小,因此我们使用一个LIst装合并区间,每次add,最后再使用LIst.toArray()方法将其变为二维数组就可以了。

一开始我写的代码是这样的:

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[] data1, int[] data2) {
                return data1[0] - data2[0];
            }
        });
        List<int[]> temp = new ArrayList<int[]>();
        temp.add(intervals[0]);
        for(int i=0;i<intervals.length-1;i++){
            if(intervals[i][1]>=intervals[i+1][0])
                temp.get(temp.size()-1)[1] = Math.max(intervals[i][1],intervals[i+1][1]);
            else
                temp.add(intervals[i+1]);
        }
        return temp.toArray(new int[temp.size()][]);

    }
}

其中还有一个细节,我一开始写的时候,每次判断是否合并的时候是将当前遍历到的区间和下一个区间进行比较,但是如果有一个case的最后一个区间overlap了前面所有区间则比较麻烦(因为前面的区间已经都被分别add进去了)。为了解决这个问题,我们应该每次都用List中的最后一个区间与当前遍历到的下一个区间进行比较。


错误结果

正确的代码如下:

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[] data1, int[] data2) {
                return data1[0] - data2[0];
            }
        });
        List<int[]> temp = new ArrayList<int[]>();
        temp.add(intervals[0]);
        for(int i=0;i<intervals.length-1;i++){
            if(temp.get(temp.size()-1)[1]>=intervals[i+1][0])
                temp.get(temp.size()-1)[1] = Math.max(temp.get(temp.size()-1)[1],intervals[i+1][1]);
            else
                temp.add(intervals[i+1]);
        }
        return temp.toArray(new int[temp.size()][]);

    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)