# 0057. 插入区间
### 题目地址(57. 插入区间)
### 题目描述
```
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。
注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
```
### 前置知识
* 排序
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 排序
#### 思路
一个简单的思路是将 intervals 和 newInterval 合并成一个数组并排序，那么问题就和 [56. 合并区间](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/56.merge-intervals) 类似，而[56. 合并区间](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/56.merge-intervals) 是一个中等题，思路参考 [56. 合并区间](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/56.merge-intervals) 即可。
#### 代码
* 语言支持: Python3
```py
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.append(newInterval)
intervals.sort(key=lambda a: a[0])
def intersected(a, b):
if a[0] > b[1] or a[1] < b[0]:
return False
return True
def mergeTwo(a, b):
return [min(a[0], b[0]), max(a[1], b[1])]
i = 0
while i < len(intervals) - 1:
cur = intervals[i]
next = intervals[i + 1]
if intersected(cur, next):
intervals[i] = None
intervals[i + 1] = mergeTwo(cur, next)
i += 1
return list(filter(lambda x: x, intervals))
```
**复杂度分析**
* 时间复杂度：由于采用了排序，因此复杂度大概为 $O(NlogN)$
* 空间复杂度：$O(1)$
### 一次扫描
#### 思路
由于没有卡时间复杂度，因此上面的代码也不会超时。但是实际的面试可能并不会通过，我们必须考虑线性时间复杂度的做法。
> 力扣有很多测试用例卡的不好的题目，以至于暴力法都可以过，但是大家不要抱有侥幸心理，否则真真实面试的时候会后悔。
newInterval 相对于 intervals 的位置关系有多种：
* newInterval 在左侧
* newInterval 在右侧
* newInterval 在中间
而 newInterval 在中间又分为相交和不相交，看起来比较麻烦，实际却不然。来看下我的具体算法。
算法描述：
* 从左往右遍历，对于遍历到的每一项姑且称之为 interval。
* 如果 interval 在 newInterval 左侧不相交，那么不断 push interval 到 ans。
* 否则不断合并 interval 和 newInterval，直到合并之后的新区间和 interval 不重合，将合并后的**大区间** push 到 ans。融合的方法参考上方 56 题。
* 后面不可能发生重合了（题目保证了），因此直接将后面的 interval 全部添加到 ans 即可
* 最终返回 ans
#### 代码
* 语言支持: Python3
```py
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
i, n = 0, len(intervals)
ans = []
def intersected(a, b):
if a[0] > b[1] or a[1] < b[0]:
return False
return True
# 前
while i < n and intervals[i][1] < newInterval[0]:
ans.append(intervals[i])
i += 1
# 中
while i < n and intersected(intervals[i], newInterval):
newInterval = [min(intervals[i][0], newInterval[0]),
max(intervals[i][1], newInterval[1])]
i += 1
ans.append(newInterval)
# 后
while i < n:
ans.append(intervals[i])
i += 1
return ans
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/57.insert-interval.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.