https://leetcode-cn.com/problems/insert-interval/
给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 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. 合并区间 类似,而56. 合并区间 是一个中等题,思路参考 56. 合并区间 即可。
- 语言支持: Python3
classSolution: definsert(self, intervals: List[List[int]], newInterval: List[int]) ->List[List[int]]: intervals.append(newInterval) intervals.sort(key=lambdaa: a[0]) defintersected(a, b): ifa[0] >b[1] ora[1] <b[0]: returnFalsereturnTruedefmergeTwo(a, b): return [min(a[0], b[0]), max(a[1], b[1])] i=0whilei<len(intervals) -1: cur=intervals[i] next=intervals[i+1] ifintersected(cur, next): intervals[i] =Noneintervals[i+1] =mergeTwo(cur, next) i+=1returnlist(filter(lambdax: 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
classSolution: definsert(self, intervals: List[List[int]], newInterval: List[int]) ->List[List[int]]: i, n=0, len(intervals) ans= [] defintersected(a, b): ifa[0] >b[1] ora[1] <b[0]: returnFalsereturnTrue# 前whilei<nandintervals[i][1] <newInterval[0]: ans.append(intervals[i]) i+=1# 中whilei<nandintersected(intervals[i], newInterval): newInterval= [min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])] i+=1ans.append(newInterval) # 后whilei<n: ans.append(intervals[i]) i+=1returnans
复杂度分析
- 时间复杂度:$O(N)$
- 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。