当前位置：首页 > news >正文

【LeetCode面试150】——57插入区间

news 来源：原创 2025/7/15 19:07:55

博客昵称：沈小农学编程

作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！

PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

题目难度：中等

默认优化目标：最小化时间复杂度。

Python默认为Python3。

1 题目描述

2 题目分析

3 代码实现

3.1 模拟

参考文献

1 题目描述

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

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

返回插入之后的 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 <= 104

intervals[i].length == 2

0 <= starti <= endi <= 105

intervals 根据 starti 按升序排列

newInterval.length == 2

0 <= start <= end <= 105

2 题目分析

输入是一个无重复的区间数组intervals，输出是将一个新区间插入后的新的无重复的区间newInterval数组ans。这道题的核心一个是判断插入位置，一个是合并重复区间。合并重复区间在56合并区间中已有具体实现。

3 代码实现

3.1 模拟

首先我们来确定新区间的插入位置。记newInterval=[new_left,new_right]，新插入的位置的区间记为pos_start=[pos_left,pos_right]。我们寻找pos_right≤new_left的位置作为插入位置。如果不存在，则在数组首位置插入。

然后进行去重，有三种情况：

① newInterval和所有intervals内的区间都不重复

② newInterval和intervals内的区间有部分重复

③ newInterval和intervals内的一个区间完全重复

这些我们只需要判断什么情况下不能合并就行，其余情况合并。当区间的右端点小于new_left，new_right的右端点小于下一个区间的左端点，不能合并。其余情况合并。

时间复杂度O(n)，空间复杂度O(1)。

算法流程图如下

C++代码实现

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {// 处理空的intervals列表的特殊情况if (intervals.empty()) {intervals.push_back(newInterval);return intervals;}
// 插入新区间bool inserted = false;for (int i = 0; i < intervals.size(); i++) {if (intervals[i][1] >= newInterval[0]) {intervals.insert(intervals.begin() + i, newInterval);inserted = true;break;}}
// 如果newInterval没有被插入（这种情况发生在newInterval是最大的区间时）if (!inserted) {intervals.push_back(newInterval);}
// 合并重叠区间vector<vector<int>> ans;ans.push_back(intervals[0]); // 从第一个区间开始
for (int i = 1; i < intervals.size(); i++) {int L = intervals[i][0], R = intervals[i][1];if (ans.back()[1] < L) {ans.push_back({L, R});} else {ans.back()[1] = max(ans.back()[1], R);ans.back()[0] = min(ans.back()[0], L);}}return ans;}
};

Python代码实现

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:# 处理空的 intervals 列表的特殊情况if not intervals:return [newInterval]
# 插入新区间inserted = Falsefor i in range(len(intervals)):if intervals[i][1] >= newInterval[0]:intervals.insert(i, newInterval)inserted = Truebreak
# 如果 newInterval 没有被插入（这种情况发生在 newInterval 是最大的区间时）if not inserted:intervals.append(newInterval)
# 合并重叠区间ans = [intervals[0]]  # 从第一个区间开始
for i in range(1, len(intervals)):L, R = intervals[i]if ans[-1][1] < L:ans.append([L, R])else:ans[-1][1] = max(ans[-1][1], R)ans[-1][0] = min(ans[-1][0], L)
return ans

参考文献

力扣面试经典150题

力扣官方题解

1 题目描述

2 题目分析

3 代码实现

3.1 模拟

参考文献

相关文章：