57_插入区间

类型：数组

• 57. 插入区间 💛 ⭐

  https://leetcode-cn.com/problems/insert-interval/

  ❓ 给你一个 无重叠的 *，*按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

  输入：intervals = 1,3, newInterval = [2,5] 输出：1,5

  💡 模拟

  class Solution:
      def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
          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

  时间复杂度：O(n)，空间复杂度：O(1)