题目

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

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

示例 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 <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^5
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/insert-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

做过了「2276. 统计区间中的整数数目」回来复习，顺着那道题的思路就有了下面的代码一，先二分查找到最后一个可能重叠的区间，然后往前找到第一个重叠的区间，将这个范围之内的区间全部合并，改为新的合并后的区间，返回结果。

代码

代码一

  1. class Solution {
  2.     public int[][] insert(int[][] intervals, int[] newInterval) {
  3.         int n = intervals.length;
  4.         // 这里必须对空数组特判，否则二分的后判会下标溢出
  5.         if (n == 0) {
  6.             return new int[][] {newInterval};
  7.         }
  8.         // end为最后一个「可能」和newInterval重叠的区间的下标
  9.         // 注意是可能，因为可能没有，不过即使没有，下面的逻辑也可以统一，因此即使end为-1也不用单独讨论
  10.         // 二分找到最后一个不大于newInterval[1]的区间的右端点，返回下标
  11.         int end = bsearch(intervals, newInterval[1]);
  12.         int left = newInterval[0];
  13.         int right = newInterval[1];
  14.         // 找到第一个和newInterval重叠的区间，因为最后还会--，所以start+1才是第一个重叠的区间
  15.         int start = end;
  16.         while (start >= 0 && intervals[start][1] >= left) {
  17.             left = Math.min(left, intervals[start][0]);
  18.             right = Math.max(right, intervals[start][1]);
  19.             start--;
  20.         }
  21.         List<int[]> ans = new ArrayList<>();
  22.         // [0,start]和[end+1,n-1]这些区间是和newInterval不重叠的
  23.         for (int i = 0; i <= start; i++) {
  24.             ans.add(intervals[i]);
  25.         }
  26.         // 在这里加入合并后的新区间
  27.         ans.add(new int[] {left, right});
  28.         for (int i = end + 1; i < n; i++) {
  29.             ans.add(intervals[i]);
  30.         }
  31.         return ans.toArray(new int[0][]);
  32.     }
  34.     private int bsearch(int[][] intervals, int num) {
  35.         int l = 0;
  36.         int r = intervals.length - 1;
  37.         while (l < r) {
  38.             int mid = l + (r - l + 1) / 2;
  39.             if (intervals[mid][0] > num) {
  40.                 r = mid - 1;
  41.             } else {
  42.                 l = mid;
  43.             }
  44.         }
  45.         if (intervals[l][0] <= num) {
  46.             return l;
  47.         }
  48.         return -1;
  49.     }
  50. }

代码二(推荐)

上面的方法即使用了二分，最坏时间仍然是O(n)，所以不如直接遍历，不使用二分，代码简洁一些

  1. class Solution {
  2.     public int[][] insert(int[][] intervals, int[] newInterval) {
  3.         int n = intervals.length;
  4.         List<int[]> ans = new ArrayList<>();
  5.         int left = newInterval[0];
  6.         int right = newInterval[1];
  7.         int i = 0;
  8.         // intervals[i][0] <= newInterval[1]表示遍历到最后一个可能重叠的区间就停止
  9.         for (; i < n && intervals[i][0] <= newInterval[1]; i++) {
  10.             // 将newInterval左边的和其不重叠的区间直接添加到结果中
  11.             if (intervals[i][1] < newInterval[0]) {
  12.                 ans.add(intervals[i]);
  13.             } else {
  14.                 // 对于重叠的区间，计算新区间的左右端点
  15.                 left = Math.min(left, intervals[i][0]);
  16.                 right = Math.max(right, intervals[i][1]);
  17.             }
  18.         }
  19.         // 加入合并后的区间
  20.         ans.add(new int[]{left, right});
  21.         // 再加入newInterval右侧不重叠的区间
  22.         for (int j = i; j < n; j++) {
  23.             ans.add(intervals[j]);
  24.         }
  25.         return ans.toArray(new int[0][]);
  26.     }
  27. }