472，插入区间

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

If we cease to believe in love, why would we want to live?

如果我们不相信爱，那又为何而活呢？

问题描述

给出一个无重叠的，按照区间起始端点排序的区间列表。

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

示例 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部分，左边不重合的（如果有）添加到集合list中，右边不重合的（如果有）也添加到集合list中，然后再合并中间的，这里以示例2为例画个图看一下

原理很简单，来看下代码

 1public int[][] insert(int[][] intervals, int[] newInterval) {
 2    //边界条件判断
 3    if (intervals.length == 0)
 4        return new int[][]{newInterval};
 5    List<int[]> resList = new ArrayList<>();
 6
 7    //一个从左边开始找不重合的
 8    int left = 0;
 9    //一个从右边开始找不重合的
10    int right = intervals.length - 1;
11
12    //左边不重合的添加到list中
13    while (left < intervals.length && intervals[left][1] < newInterval[0]) {
14        resList.add(intervals[left++]);
15    }
16
17    //右边不重合的添加到list中
18    while (right >= 0 && intervals[right][0] > newInterval[1]) {
19        resList.add(left, intervals[right--]);
20    }
21
22    //下面一大坨是合并中间重合的，注意一些边界条件的判断
23    int[] newArr = new int[2];
24    newArr[0] = left >= intervals.length ? newInterval[0] : Math.min(intervals[left][0], newInterval[0]);
25    newArr[1] = right < 0 ? newInterval[1] : Math.max(intervals[right][1], newInterval[1]);
26    resList.add(left, newArr);
27
28    //这一大坨是把list转二维数组
29    int[][] resArr = new int[resList.size()][2];
30    for (int i = 0; i < resList.size(); i++) {
31        resArr[i] = resList.get(i);
32    }
33    return resArr;
34}
35

逐步合并

上面一种方式是先把两边不重合的添加到集合list中，之后在合并中间的。这里还可以从左边开始把不重合的（如果有不重合的）添加到集合list中，如果遇到重合的就找出重合的范围然后再添加到集合中，最后再把后面不重合的（如果有）添加到集合list中。

 1public int[][] insert(int[][] intervals, int[] newInterval) {
 2    List<int[]> resList = new ArrayList<>();
 3    int i = 0;
 4    //先把前面不重合的添加到list中
 5    while (i < intervals.length && intervals[i][1] < newInterval[0])
 6        resList.add(intervals[i++]);
 7
 8    int mergeStar = newInterval[0];
 9    int mergeEnd = newInterval[1];
10    //前面不重合的都添加到集合list中了，从这里开始就出现重合了，我们要找到重合的开始和结束值
11    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
12        mergeStar = Math.min(mergeStar, intervals[i][0]);
13        mergeEnd = Math.max(mergeEnd, intervals[i][1]);
14        i++;
15    }
16    //然后再把重合的添加到list中
17    resList.add(new int[]{mergeStar, mergeEnd});
18
19    //把剩下的在添加到集合list中
20    while (i < intervals.length)
21        resList.add(intervals[i++]);
22
23    //这一大坨是把list转二维数组
24    int[][] resArr = new int[resList.size()][2];
25    for (int j = 0; j < resList.size(); j++) {
26        resArr[j] = resList.get(j);
27    }
28    return resArr;
29}