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^4intervals[i].length == 20 <= intervals[i][0] <= intervals[i][1] <= 10^5intervals 根据 intervals[i][0] 按 升序 排列newInterval.length == 20 <= newInterval[0] <= newInterval[1] <= 10^5 解题思路 一次遍历

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

关键点：

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

具体步骤：

初始化结果列表遍历原区间列表，分三种情况处理： 当前区间在新区间之前（无重叠）当前区间与新区间重叠当前区间在新区间之后（无重叠） 根据情况将区间添加到结果列表 图解思路 算法步骤分析表 步骤当前区间新区间结果列表说明初始[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 = 0 n = 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 += 1 result.append(newInterval) # 添加所有在新区间之后的区间 while i < n: result.append(intervals[i]) i += 1 return 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 ms16.9 MB性能最优Python44 ms17.5 MB代码简洁C#148 ms43.2 MB可读性好 代码亮点 🎯 一次遍历完成插入和合并💡 无需额外排序🔍 优雅处理边界情况🎨 代码结构清晰，逻辑简洁 常见错误分析 🚫 忘记处理空数组的情况🚫 合并区间时未更新边界🚫 未正确处理新区间的插入位置🚫 重叠判断条件错误 解法对比 解法时间复杂度空间复杂度优点缺点一次遍历O(n)O(1)最优解需要仔细处理边界排序后合并O(nlogn)O(1)思路简单效率低二分查找插入O(logn)O(1)查找快实现复杂 相关题目 合并区间 - 中等会议室 - 简单会议室 II - 中等Range 模块 - 困难