題目：

給你一個?無重疊的?，按照區(qū)間起始端點排序的區(qū)間列表。

在列表中插入一個新的區(qū)間，你需要確保列表中的區(qū)間仍然有序且不重疊（如果有必要的話，可以合并區(qū)間）。

來源：力扣（LeetCode）
鏈接：力扣

示例：

示例 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]]

解釋：這是因為新的區(qū)間 [4,8] 與 [3,5],[6,7],[8,10]?重疊。

示例 3：

輸入：intervals = [], newInterval = [5,7]
輸出：[[5,7]]

示例4：

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

輸出：[[1,5]]

示例5：

輸入：intervals = [[1,5]], newInterval = [2,7]

輸出：[[1,7]]

解法：

首先處理特殊情況，如果intervals為空，返回newInterval；如果newInterval的右區(qū)間比intervals第1個區(qū)間的左區(qū)間小，說明newInterval比intervals中所有區(qū)間小，返回[newInterval] + intervals；同理，如果newInterval的左區(qū)間比intervals第最后一個區(qū)間的右區(qū)間大，返回intervals + [newInterval]。剩下的情況進入算法，結果存在result。

遍歷intervals，如果newInterval的左區(qū)間大當前區(qū)間的右區(qū)間，說明沒有交集，添加當前區(qū)間到result。否則，記錄交集的左區(qū)間為當前區(qū)間和newInterval中小的左區(qū)間，設為left。接著從當前區(qū)間開始遍歷剩下intervals，如果newInterval的右區(qū)間大于當前區(qū)間的右區(qū)間，說明newInterval的范圍可以覆蓋當前區(qū)間，所以可以跳過當前區(qū)間，如果當前已經是最有一個區(qū)間，設right為newInterval的右區(qū)間，然后添加[left,?right]到result，返回result。如果newInterval的右區(qū)間小于等于當前區(qū)間的右區(qū)間，說明和newInterval有交集的最大右區(qū)間已出現(xiàn)，如果newInterval的右區(qū)間大于等于當前區(qū)間和左區(qū)間，設right為newInterval和當前區(qū)間中大的右區(qū)間，添加[left,?right]到result，然后把后面區(qū)間也加入result。如果newInterval的右區(qū)間小于當前區(qū)間和左區(qū)間，說明newInterval和當前區(qū)間沒有交集，這里對應兩種情況，分別是newInterval的左區(qū)間和前面區(qū)間有交集以及newInterval的左區(qū)間和前面區(qū)間沒有交集，所以設right為newInterval的右區(qū)間，然后添加[left,?right]到result，再把后面區(qū)間也加入result。

代碼：

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:if len(intervals) == 0:return [newInterval]if newInterval[1] < intervals[0][0]:return [newInterval] + intervalsif newInterval[0] > intervals[-1][1]:return intervals + [newInterval]result = []for index1, interval1 in enumerate(intervals):if newInterval[0] <= interval1[1]:left = min(interval1[0], newInterval[0])for index2, interval2 in enumerate(intervals[index1:]):if newInterval[1] <= interval2[1]:if newInterval[1] >= interval2[0]:result.append([left, max(interval2[1], newInterval[1])])else:result.append([left, newInterval[1]])result.append(interval2)if index2 != len(intervals[index1:]) - 1:result.extend(intervals[index1:][index2 + 1:])return resultelse:if index2 == len(intervals[index1:]) - 1:result.append([left, newInterval[1]])return resultelse:result.append(interval1)