力扣57. 插入区间

描述

力扣57. 插入区间
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 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] 重叠。

提示：
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 105

方法：遍历融合区间

思路：
记需要插入的区间newInterval的起点为leftNum,终点为RightNum.我们遍历被插入区间intervals，如果插入区间和被插入区间存在重叠，那么我们取并集直接融合区间。有重叠我们就融合，直到没有重叠，那么就将最后的区间放入答案集合。具体代码实现及详细注释如下。
具体实现及注释：

class Solution {
   public int[][] insert(int[][] intervals, int[] newInterval) {
       //从插入区间中取出起始点的值
       int leftNum = newInterval[0];
       int rightNum = newInterval[1];
       //这个是用来标记区间是否已入答案集合，我们在后文结合具体代码解释
       boolean flag = false;
       //临时存放答案的集合
       List<int[]> ans = new ArrayList<>();
       for (int[] interval : intervals) {
           //如果newInterval的起点大于interval的终点，则代表没有重合，将interval入答案集合。
           if (leftNum > interval[1]) ans.add(interval);
           //如果newInterval终点第一次小于interval的起点，则找到插入区间的位置，均入答案集合
           else if (rightNum < interval[0]) {
               //这个flag是用来标记newInterval是否已经插入过区间。因为一旦当rightNum < interval[0]
               //rightNum必然也小于后续interval数组的起点，但我们只需要第一次插入newInterval，所以用flag标记，当第一次插入后将flag修改为true，则后续不会进行此操作
   
               if (flag == false) {
                   ans.add(new int[]{leftNum, rightNum});
                   flag = true;
               }
               ans.add(interval);
               //这个便是有交集的情况，我们融合区间取并集
           } else {
               leftNum = Math.min(leftNum, interval[0]);
               rightNum = Math.max(rightNum, interval[1]);
           }
       }
       //这个是因为存在无法满足rightNum < interval[0]，比如intervals为空，或者rightNum比intervals区间中最大的数都大，这些情况直接将其入结果集合即可
       if (flag == false) ans.add(new int[]{leftNum, rightNum});
       int[][] finalAns = new int[ans.size()][2];
       for (int i = 0; i < finalAns.length; i++) {
           finalAns[i] = ans.get(i);
       }
       return finalAns;
   }   
}

原文地址：https://blog.csdn.net/dastatham/article/details/142548754

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！