LEETCODE 56. Merge Intervals 解题思路分析

题目大意：

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 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.jp/problemdetail.php?id=56

解题思路分析：

本题需要先对数组进行一次排序，排序规则是区间开始坐标由小到大升序排序。排序后我们能够保证对于任意一个区间，它的开始坐标一定大于等于前区间的开始坐标，这样相邻2个区间的关系会有以下三种可能：

1. 当前区间开始坐标大于前区间结束坐标，说明2区间不相交从而无法合并，将前区间加入返回结果。
2. 当前区间开始坐标小于等于前区间结束坐标，说明2区间存在交集，交集范围是当前区间开始坐标到前区间结束坐标之间，此时可以合并，将前区间结束坐标更改为当前区间结束坐标。
3. 当前区间结束坐标小于等于前区间结束坐标，说明当前区间是前区间的子集，当前区间可被忽略。

实现代码：

public int[][] merge(int[][] intervals) {
    // 如果intervals为空，返回空
    if(intervals.length==0) return new int[0][0];
    // 按区间开始坐标升序排序
    Arrays.sort(intervals, (x1, x2)->x1[0]-x2[0]);
    // 返回结果
    List<int[]> list = new ArrayList<>();
    // 前区间
    int[] pre = intervals[0];
    // 从第二个区间开始循环与前区间比较
    for(int i=1;i<intervals.length;i++){
        // 当前区间
        int[] current = intervals[i];
        // 当前区间开始坐标大于前区间结束坐标，无交集
        if(current[0] > pre[1]){
            // 将前区间加入返回结果
            list.add(pre);
            // 将当前区间设置为前区间
            pre=current;
        }else if(current[1]>=pre[1]){
            // 当前区间结束坐标大于等于前区间结束坐标
            // 另外两个以确定条件：
            // 1. 当前区间开始坐标小于等于前区间结束坐标（上面if的另外分支）
            // 2. 当前区间开始坐标大于等于前区间开始坐标（因为排序）
            // 此时2区间相交，将前区间结束坐标更改为当前区间结束坐标
            pre[1]=current[1];
        }
    }
    // 将最后一个区间加入返回结果
    list.add(pre);
    // 将list转化为数组返回
    int[][] res = new int[list.size()][2];
    for(int i=0;i<list.size();i++){
        res[i] = list.get(i);
    }
    return res;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 90.48% of Java online submissions for Merge Intervals.

Memory Usage: 40.9 MB, less than 63.77% of Java online submissions for Merge Intervals.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-56-merge-intervals-解题思路分析/