力扣：57. 插入区间（Python3）

题目：

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

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

来源：力扣（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]]

解释：这是因为新的区间 [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的右区间比intervals第1个区间的左区间小，说明newInterval比intervals中所有区间小，返回[newInterval] + intervals；同理，如果newInterval的左区间比intervals第最后一个区间的右区间大，返回intervals + [newInterval]。剩下的情况进入算法，结果存在result。

遍历intervals，如果newInterval的左区间大当前区间的右区间，说明没有交集，添加当前区间到result。否则，记录交集的左区间为当前区间和newInterval中小的左区间，设为left。接着从当前区间开始遍历剩下intervals，如果newInterval的右区间大于当前区间的右区间，说明newInterval的范围可以覆盖当前区间，所以可以跳过当前区间，如果当前已经是最有一个区间，设right为newInterval的右区间，然后添加[left, right]到result，返回result。如果newInterval的右区间小于等于当前区间的右区间，说明和newInterval有交集的最大右区间已出现，如果newInterval的右区间大于等于当前区间和左区间，设right为newInterval和当前区间中大的右区间，添加[left, right]到result，然后把后面区间也加入result。如果newInterval的右区间小于当前区间和左区间，说明newInterval和当前区间没有交集，这里对应两种情况，分别是newInterval的左区间和前面区间有交集以及newInterval的左区间和前面区间没有交集，所以设right为newInterval的右区间，然后添加[left, right]到result，再把后面区间也加入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)