LeetCode第57题_插入区间

LeetCode 第57题：插入区间

题目描述

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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]]

提示

• 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

解题思路

一次遍历

这道题是第56题"合并区间"的变体，但不需要对区间进行排序，因为输入已经是有序的。我们只需要找到新区间应该插入的位置，然后处理可能的重叠情况。

关键点：

1. 输入区间列表已经按起始位置排序
2. 需要处理与新区间的重叠情况
3. 一次遍历即可完成插入和合并
4. 注意处理边界情况

具体步骤：

1. 初始化结果列表
2. 遍历原区间列表，分三种情况处理：
   • 当前区间在新区间之前（无重叠）
   • 当前区间与新区间重叠
   • 当前区间在新区间之后（无重叠）
3. 根据情况将区间添加到结果列表

图解思路

算法步骤分析表

步骤	当前区间	新区间	结果列表	说明
初始	[1,2]	[4,8]	[[1,2]]	无重叠，保留当前区间
第1步	[3,5]	[4,8]	[[1,2],[3,8]]	有重叠，合并区间
第2步	[6,7]	[3,8]	[[1,2],[3,8]]	有重叠，继续合并
第3步	[8,10]	[3,8]	[[1,2],[3,10]]	有重叠，继续合并
第4步	[12,16]	[3,10]	[[1,2],[3,10],[12,16]]	无重叠，添加当前区间

状态/情况分析表

情况	输入	输出	说明
空列表	[], [5,7]	[[5,7]]	直接返回新区间
无重叠	[[1,3],[6,9]], [4,5]	[[1,3],[4,5],[6,9]]	直接插入新区间
部分重叠	[[1,3],[6,9]], [2,5]	[[1,5],[6,9]]	需要合并重叠区间
完全重叠	[[1,5]], [2,3]	[[1,5]]	新区间被完全包含

代码实现

C# 实现

public class Solution {public int[][] Insert(int[][] intervals, int[] newInterval) {var result = new List<int[]>();bool inserted = false;// 处理空数组的情况if (intervals.Length == 0) {return new int[][] { newInterval };}foreach (var interval in intervals) {// 当前区间在新区间之前if (interval[1] < newInterval[0]) {result.Add(interval);}// 当前区间在新区间之后else if (interval[0] > newInterval[1]) {if (!inserted) {result.Add(newInterval);inserted = true;}result.Add(interval);}// 有重叠，合并区间else {newInterval[0] = Math.Min(newInterval[0], interval[0]);newInterval[1] = Math.Max(newInterval[1], interval[1]);}}// 如果新区间还没有插入，将其添加到末尾if (!inserted) {result.Add(newInterval);}return result.ToArray();}
}

C# 执行结果：

• 执行用时：148 ms
• 内存消耗：43.2 MB

Python 实现

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:result = []i = 0n = len(intervals)# 处理空数组的情况if n == 0:return [newInterval]# 添加所有在新区间之前的区间while i < n and intervals[i][1] < newInterval[0]:result.append(intervals[i])i += 1# 合并重叠的区间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 += 1result.append(newInterval)# 添加所有在新区间之后的区间while i < n:result.append(intervals[i])i += 1return result

Python 执行结果：

• 执行用时：44 ms
• 内存消耗：17.5 MB

C++ 实现

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();// 处理空数组的情况if (n == 0) {result.push_back(newInterval);return result;}// 添加所有在新区间之前的区间while (i < n && intervals[i][1] < newInterval[0]) {result.push_back(intervals[i]);i++;}// 合并重叠的区间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);// 添加所有在新区间之后的区间while (i < n) {result.push_back(intervals[i]);i++;}return result;}
};

C++ 执行结果：

• 执行用时：12 ms
• 内存消耗：16.9 MB

性能对比

语言	执行用时	内存消耗	特点
C++	12 ms	16.9 MB	性能最优
Python	44 ms	17.5 MB	代码简洁
C#	148 ms	43.2 MB	可读性好

代码亮点

1. 🎯 一次遍历完成插入和合并
2. 💡 无需额外排序
3. 🔍 优雅处理边界情况
4. 🎨 代码结构清晰，逻辑简洁

常见错误分析

1. 🚫 忘记处理空数组的情况
2. 🚫 合并区间时未更新边界
3. 🚫 未正确处理新区间的插入位置
4. 🚫 重叠判断条件错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
一次遍历	O(n)	O(1)	最优解	需要仔细处理边界
排序后合并	O(nlogn)	O(1)	思路简单	效率低
二分查找插入	O(logn)	O(1)	查找快	实现复杂

相关题目

• 合并区间 - 中等
• 会议室 - 简单
• 会议室 II - 中等
• Range 模块 - 困难