0057. 插入区间

题目地址(57. 插入区间)

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



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

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)$

最后更新于