Medium

题目描述

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

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

示例 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 <= starti <= endi <= 10^5
  • intervals 根据 starti 按升序排列
  • newInterval.length == 2
  • 0 <= start <= end <= 10^5

解题思路

这道题考查区间合并的经典问题。由于原区间数组已经按起始位置排序且无重叠，我们可以采用线性扫描的方法。

核心思路：

  1. 三个阶段处理：将整个过程分为三个阶段

    • 添加所有结束位置在新区间开始位置之前的区间（无重叠）
    • 合并与新区间有重叠的所有区间
    • 添加所有开始位置在新区间结束位置之后的区间（无重叠）

  2. 重叠判断：两个区间 [a,b] 和 [c,d] 重叠的条件是 a <= d && c <= b

  3. 合并策略：当发现重叠时，更新新区间的边界：

    • 左边界取较小值：min(newInterval[0], interval[0])
    • 右边界取较大值：max(newInterval[1], interval[1])

算法步骤：

  • 遍历原区间数组，对每个区间判断与新区间的关系
  • 如果当前区间完全在新区间左侧，直接添加到结果
  • 如果存在重叠，合并到新区间中
  • 如果当前区间完全在新区间右侧，添加合并后的新区间，然后添加剩余所有区间

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑结果数组），是最优解法。

代码实现

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0;
        int n = intervals.size();
        
        // Add all intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }
        
        // Merge overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.push_back(newInterval);
        
        // Add all intervals that start after newInterval ends
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }
        
        return result;
    }
};

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        n = len(intervals)
        
        # Add all intervals that end before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        
        # Merge overlapping intervals with newInterval
        while i < n 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)
        
        # Add all intervals that start after newInterval ends
        while i < n:
            result.append(intervals[i])
            i += 1
        
        return result

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new List<int[]>();
        int i = 0;
        int n = intervals.Length;
        
        // Add all intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.Add(intervals[i]);
            i++;
        }
        
        // Merge overlapping intervals with newInterval
        while (i < n && 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.Add(newInterval);
        
        // Add all intervals that start after newInterval ends
        while (i < n) {
            result.Add(intervals[i]);
            i++;
        }
        
        return result.ToArray();
    }
}

var insert = function(intervals, newInterval) {
    const result = [];
    let i = 0;
    const n = intervals.length;
    
    // Add all intervals that end before newInterval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }
    
    // Merge overlapping intervals with newInterval
    while (i < n && 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);
    
    // Add all intervals that start after newInterval ends
    while (i < n) {
        result.push(intervals[i]);
        i++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次原区间数组，每个区间最多被访问一次
空间复杂度O(1)只使用了常数个额外变量，不考虑结果数组的空间

相关题目