LeetCode 题解工作台
插入区间
给你一个 无重叠的 ， 按照区间起始端点排序的区间列表 intervals ，其中 intervals[i] = [start i , end i ] 表示第 i 个区间的开始和结束，并且 intervals 按照 start i 升序排列。同样给定一个区间 newInterval = [start…
1
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·driven
答案摘要
我们可以先将新区间 `newInterval` 加入到区间列表 `intervals` 中，然后按照区间合并的常规方法进行合并。 时间复杂度 $O(n \times \log n)$，空间复杂度 。其中 是区间的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 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 <= 104intervals[i].length == 20 <= starti <= endi <= 105intervals根据starti按 升序 排列newInterval.length == 20 <= start <= end <= 105
解题思路
方法一：排序 + 区间合并
我们可以先将新区间 newInterval 加入到区间列表 intervals 中，然后按照区间合并的常规方法进行合并。
时间复杂度 ，空间复杂度 。其中 是区间的数量。
class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
def merge(intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
ans = [intervals[0]]
for s, e in intervals[1:]:
if ans[-1][1] < s:
ans.append([s, e])
else:
ans[-1][1] = max(ans[-1][1], e)
return ans
intervals.append(newInterval)
return merge(intervals)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Look for efficiency in finding the insertion point, particularly using binary search for the best performance.
- question_mark
Evaluate the candidate's understanding of merging intervals and their ability to handle edge cases such as no overlaps or full array merges.
- question_mark
Assess the candidate's grasp of time and space complexity analysis, especially in terms of managing large inputs.
常见陷阱
外企场景- error
Failing to consider edge cases such as inserting an interval that doesn't overlap with any existing ones.
- error
Not merging overlapping intervals correctly, which might leave the array unsorted or with unnecessary intervals.
- error
Overcomplicating the solution with unnecessary data structures, making it more complex than needed.
进阶变体
外企场景- arrow_right_alt
Handling intervals that are already merged or include no overlaps at all.
- arrow_right_alt
Working with unsorted intervals before insertion, requiring an initial sorting step.
- arrow_right_alt
Inserting multiple intervals at once instead of just one new interval.