LeetCode_区间问题_中等_57.插入区间

港控/mmm° 2023-10-06 19:00 97阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个无重叠的，按照区间起始端点排序的区间列表。  
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

**示例 1：**  
输入：intervals = \[\[1,3\],\[6,9\]\], newInterval = \[2,5\]  
输出：\[\[1,5\],\[6,9\]\]

**示例 2：**  
输入：intervals = \[\[1,2\],\[3,5\],\[6,7\],\[8,10\],\[12,16\]\], newInterval = \[4,8\]  
输出：\[\[1,2\],\[3,10\],\[12,16\]\]  
解释：这是因为新的区间 \[4,8\] 与 \[3,5\],\[6,7\],\[8,10\] 重叠。

**示例 3：**  
输入：intervals = \[\], newInterval = \[5,7\]  
输出：\[\[5,7\]\]

**示例 4：**  
输入：intervals = \[\[1,5\]\], newInterval = \[2,3\]  
输出：\[\[1,5\]\]

**示例 5：**  
输入：intervals = \[\[1,5\]\], newInterval = \[2,7\]  
输出：\[\[1,7\]\]

**提示：**  
0 <= intervals.length <= 104  
intervals\[i\].length == 2  
0 <= intervals\[i\]\[0\] <= intervals\[i\]\[1\] <= 105  
intervals 根据 intervals\[i\]\[0\] 按升序排列  
newInterval.length == 2  
0 <= newInterval\[0\] <= newInterval\[1\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/insert-interval

## 2.思路 ##

（1）区间问题  
分析题目，先定义用于保存结果的动态数组 res，之后可将本题的求解过程分主要为以下 3 个阶段：**将开始的非重叠区间加入 res**、**处理插入的新区间并将有关的区间加入 res**、**将剩余的非重叠区间加入 res**，具体步骤如下：

*  定义变量 left 和 right，分别表示区间 newInterval 的左右端点，此外定义初始值为 0 的变量 i，用于遍历 intervals 中的区间；
 *  **将开始的非重叠区间加入res**：若区间 intervals\[i\] 的右端点小于 left，则该区间不可能与 newInterval 重叠，那么将其添加到 res 中，然后 i++，继续判断下一个区间，直到 i ≥ intervals.length 或者 left ≤ intervals\[i\]\[1\] 为止；
 *  **处理插入的新区间并将有关的区间加入 res**：
    
     *  **若 i ≥ intervals.length**：则说明区间 newInterval 与任意区间 intervals\[i\] 均无重叠部分，并且 intervals 所有区间都已经加入到 res 中，此时可直接将其加入到 res 中，并且跳过剩余步骤，直接返回结果即可；
     *  **若 i＜intervals.length、left ≤ intervals\[i\]\[1\] 且 intervals\[i\]\[0\] <= right**：则说明 newInterval 至少与区间 intervals\[i\] 有重叠部分，此时求出当前合并区间的左右端点，即更新 left 和 right 的值，然后 i++，判断下一个区间与 \[left, right\] 是否有重叠部分；  
        最后将区间 \[left, right\] 加入 res 之中；
 *  **将剩余的非重叠区间加入 res**：执行 res.add(intervals\[i++\]) 直到 i ≥ intervals.length；
 *  将 res 转换为行数为 res.size()、列数为 2 的二维数组并返回即可。

## 3.代码实现（Java） ##

//思路1————区间问题
    class Solution {
        
    	public int[][] insert(int[][] intervals, int[] newInterval) {
        
    	    int length = intervals.length;
    	    //当 intervals 为空时，将 newInterval 作为结果的第一行返回即可
    	    if (length == 0) {
        
    	        return new int[][]{
        newInterval};
    	    }
    	    //定义 res，用于保存结果
    	    List<int[]> res = new ArrayList<>();
    	    // left: 区间 newInterval 的左端点  right: 区间 newInterval 的右端点
    	    int left = newInterval[0], right = newInterval[1];
    	    int i = 0;
    	    //将非重叠区间加入 res
    	    //若区间 intervals[i] 的右端点小于 left，该区间不可能与 newInterval 重叠，那么将其添加到 res 中
    	    while (i < length && intervals[i][1] < left) {
        
    	        res.add(intervals[i++]);
    	    }
    	    //若存在重叠区间，则求出最大合并区间的左右端点
    	    // intervals[i][0]    left ≤ intervals[i][1]   right  
    	    while (i < length && intervals[i][0] <= right) {
        
    	        //求出当前合并区间的左右端点，即更新 left 和 right 的值
    	        left = Math.min(left, intervals[i][0]);
    	        right = Math.max(right, intervals[i][1]);
    	        //判断下一个区间与区间 [left, right] 是否有重叠部分
    	        i++;
    	    }
    	    res.add(new int[]{
        left, right});
    	    //将剩余的非重叠区间加入 res
    	    while (i < length) {
        
    	        res.add(intervals[i++]);
    	    }
    	    return res.toArray(new int[res.size()][]);
    	}
    }