TNotes.leetcode

Appearance

0057. 插入区间【中等】

0057. 插入区间【中等】 ​

1. 📝 题目描述 ​

给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [start_i, end_i] 表示第 i 个区间的开始和结束，并且 intervals 按照 start_i 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 start_i 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 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 <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^5
  • intervals 根据 start_i 按升序排列
  • newInterval.length == 2
  • 0 <= start <= end <= 10^5

2. 🎯 s.1 - 一次遍历（三阶段合并） ​

c
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */
int** insert(int** intervals, int intervalsSize, int* intervalsColSize,
             int* newInterval, int newIntervalSize, int* returnSize,
             int** returnColumnSizes) {
    int** result = (int**)malloc(sizeof(int*) * (intervalsSize + 1));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (intervalsSize + 1));
    int idx = 0, i = 0;

    // 添加所有在 newInterval 左侧不重叠的区间
    while (i < intervalsSize && intervals[i][1] < newInterval[0]) {
        result[idx] = (int*)malloc(sizeof(int) * 2);
        result[idx][0] = intervals[i][0];
        result[idx][1] = intervals[i][1];
        (*returnColumnSizes)[idx] = 2;
        idx++;
        i++;
    }

    // 合并所有与 newInterval 重叠的区间
    while (i < intervalsSize && intervals[i][0] <= newInterval[1]) {
        if (intervals[i][0] < newInterval[0])
            newInterval[0] = intervals[i][0];
        if (intervals[i][1] > newInterval[1])
            newInterval[1] = intervals[i][1];
        i++;
    }
    result[idx] = (int*)malloc(sizeof(int) * 2);
    result[idx][0] = newInterval[0];
    result[idx][1] = newInterval[1];
    (*returnColumnSizes)[idx] = 2;
    idx++;

    // 添加所有在 newInterval 右侧不重叠的区间
    while (i < intervalsSize) {
        result[idx] = (int*)malloc(sizeof(int) * 2);
        result[idx][0] = intervals[i][0];
        result[idx][1] = intervals[i][1];
        (*returnColumnSizes)[idx] = 2;
        idx++;
        i++;
    }

    *returnSize = idx;
    return result;
}
js
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  const result = []
  let i = 0

  // 添加所有在 newInterval 左侧不重叠的区间
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i])
    i++
  }

  // 合并所有与 newInterval 重叠的区间
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0])
    newInterval[1] = Math.max(newInterval[1], intervals[i][1])
    i++
  }
  result.push(newInterval)

  // 添加所有在 newInterval 右侧不重叠的区间
  while (i < intervals.length) {
    result.push(intervals[i])
    i++
  }

  return result
}
py
class Solution:
    def insert(
        self, intervals: List[List[int]], newInterval: List[int]
    ) -> List[List[int]]:
        result = []
        i = 0

        # 添加所有在 newInterval 左侧不重叠的区间
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # 合并所有与 newInterval 重叠的区间
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)

        # 添加所有在 newInterval 右侧不重叠的区间
        while i < len(intervals):
            result.append(intervals[i])
            i += 1

        return result
  • 时间复杂度：O(n)，其中 n 是区间数组的长度，只需遍历一次
  • 空间复杂度：O(1)，不计输出数组，只使用常数额外空间

算法思路：

  • 将区间分为三组，依次处理：
  • 第一段 => 左侧不重叠：所有 end < newInterval[0] 的区间，直接加入结果
  • 第二段 => 重叠合并：所有 start <= newInterval[1] 的区间，与 newInterval 合并（取 min(start) 和 max(end)），合并完成后将 newInterval 加入结果
  • 第三段 => 右侧不重叠：剩余区间直接加入结果

Discussions