pythontip 100days-day25

Code › python
, ,

题目

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）

例子

insertInterval([[1,3],[6,9]],[2,5]) ->[[1,5],[6,9]]
insertInterval([[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]) -> [[1,2],[3,10],[12,16]]

假设

  1. 输入的参数均不为空

tips

  1. 找到插入位置
  2. 合并区间

答案

解法1

def insertInterval(intervals,newInterval):
    left, right = newInterval
    placed = False
    ans = list()
    for li, ri in intervals:
        if li > right:
            # 在插入区间的右侧且无交集
            if not placed:
                ans.append([left, right])
                placed = True
            ans.append([li, ri])
        elif ri < left:
            # 在插入区间的左侧且无交集
            ans.append([li, ri])
        else:
            # 与插入区间有交集，计算它们的并集
            left = min(left, li)
            right = max(right, ri)
    
    if not placed:
        ans.append([left, right])
    return ans

性能：

  1. 时间复杂度O(n)
  2. 空间复杂度O(n)

关键点：

  1. 找到插入位置
  2. 合并区间