[数据结构与算法]插入区间Python解法

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-interval

例：

输入：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]?重叠。

解析：

首先空判断，然后先判断插入头的位置，然后判断插入尾的位置即可。

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        res = []  # 结果
        if not intervals:  # 判空
            return [newInterval]
        i, n = 0, len(intervals)  # 指针，长度
        while i < n and intervals[i][0] <= newInterval[0]:  # 判断头部位置
            i += 1
        res = intervals[:i]  # 前面不相干的区间直接进入结果数组
        if not res or res[-1][1] < newInterval[0]:  # 判断当前结果数组的尾部
            res.append(newInterval)
        else:
            res[-1][1] = max(res[-1][1], newInterval[1])
        for j in range(i, n):  # 判断尾部位置
            if res[-1][1] < intervals[j][0]:  # 尾部小于后半段的左区间，后半段直接插入
                res += intervals[j:]
                break
            else:
                res[-1][1] = max(res[-1][1], intervals[j][1])  # 否则比较大小，合并并找出最大的右区间
        return res