博客昵称:沈小农学编程
作者简介:一名在读硕士,定期更新相关算法面试题,欢迎关注小弟!
PS:哈喽!各位CSDN的uu们,我是你的小弟沈小农,希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正,觉得好的话别忘了一键三连哦!😘
题目难度:中等
默认优化目标:最小化时间复杂度。
Python默认为Python3。
目录
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 = False
for i in range(len(intervals)):
if intervals[i][1] >= newInterval[0]:
intervals.insert(i, newInterval)
inserted = True
break
# 如果 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