LeetCode 57. 插入区间

◎

本节目标

依次追加左侧区间、合并重叠区间并保留右侧区间。

这道题位于数组与矩阵综合，并复用数组与区间中的有序边界思想。

查看原题

题意与约束

给定按左端点排序且彼此不重叠的区间，插入 newInterval，返回仍然有序且不重叠的结果。

朴素思路及瓶颈

把新区间追加到数组后，可以调用通用合并方案：重新排序全部 n + 1 个区间，再扫描合并，时间复杂度为 O(n log n)。这会重复建立输入已经保证的有序关系；既然原区间彼此不重叠，只需顺序判断它们位于新区间左侧、与之重叠还是位于右侧。

三段扫描

扫描可以自然分为三段：右端点严格小于新区间左端点的区间完全在左侧，直接追加；左端点不大于新区间右端点的区间与新区间重叠，更新新区间两端；其余区间完全在右侧，保持原顺序追加。

代码实现

两份源码都只线性扫描一次，并直接把重叠区间的边界合并到 newInterval。

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> answer;
        size_t index = 0;
        while (index < intervals.size() && intervals[index][1] < newInterval[0]) {
            answer.push_back(intervals[index++]);
        }
        while (index < intervals.size() && intervals[index][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[index][0]);
            newInterval[1] = max(newInterval[1], intervals[index][1]);
            index++;
        }
        answer.push_back(newInterval);
        while (index < intervals.size()) {
            answer.push_back(intervals[index++]);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        answer = []
        index = 0
        while index < len(intervals) and intervals[index][1] < newInterval[0]:
            answer.append(intervals[index])
            index += 1
        while index < len(intervals) and intervals[index][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[index][0])
            newInterval[1] = max(newInterval[1], intervals[index][1])
            index += 1
        answer.append(newInterval)
        answer.extend(intervals[index:])
        return answer

复杂度分析

时间复杂度为 O(n)，除返回结果外额外空间为 O(1)。

易错点

• 左侧判断没有使用严格小于，把端点相接的可合并区间提前分开。
• 合并结束后忘记追加更新后的新区间。
• 误以为输入无序而重新排序，忽略题目的已有排序前提。

模式迁移

插入区间是数组与区间中“排序后只维护当前边界”的直接变体；若输入不保证有序，应先排序或改用合并区间的框架。