56. 合并区间

朴灿烈づ我的快乐病毒、 2023-10-16 15:42 128阅读 0赞

#### 56. 合并区间 ####

*  题干描述
 *  解题思路
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

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

示例 1:

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

示例 2：

*  输入: intervals = \[\[1,4\],\[4,5\]\]
 *  输出: \[\[1,5\]\]
 *  解释: 区间 \[1,4\] 和 \[4,5\] 可被视为重叠区间。
 *  注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

## 解题思路 ##

本题的本质其实还是判断重叠区间问题。

和我们之前介绍过的**452. 用最少数量的箭引爆气球**和 **435. 无重叠区间**都是一个套路。

这几道题都是判断区间重叠，区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。

所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals\[i\]\[0\] <= intervals\[i - 1\]\[1\] 即intervals\[i\]的左边界 <= intervals\[i - 1\]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

这么说有点抽象，看图：（**注意图中区间都是按照左边界排序之后了）**  
![在这里插入图片描述][e5ba840300de4e5ba656e80877e7f641.png]  
知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

## 代码实现 ##

class Solution {
        
        // 56. 合并区间
        /**
         * 时间复杂度：O(NlogN)排序需要O(NlogN)
         * 空间复杂度：O(logN) java的内置排序是快速排序 需要O(logN)空间
         */
        public int[][] merge(int[][] intervals){
        
            List<int[]> res = new LinkedList<>();
            // 按照左边界排序
            Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
            // initial start是最小左边界
            int start = intervals[0][0];
            int rightmostRightBound = intervals[0][1];
            for(int i = 1; i < intervals.length; i++){
        
                // 如果左边界大于最大右边界
                if(intervals[i][0] > rightmostRightBound){
        
                    // 加入区间 并且更新start
                    res.add(new int[]{
        start, rightmostRightBound});
                    start = intervals[i][0];
                    rightmostRightBound = intervals[i][1];
                } else{
        
                    // 更新最大右边界
                    rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
                }
            }
            res.add(new int[]{
        start, rightmostRightBound});
            return res.toArray(new int[res.size()][]);
        }
    }

**参考资料**：[代码随想录-56. 合并区间][-56.]

[Link 1]: https://leetcode.cn/problems/merge-intervals/
[e5ba840300de4e5ba656e80877e7f641.png]: https://img-blog.csdnimg.cn/e5ba840300de4e5ba656e80877e7f641.png
[-56.]: https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE