题解 | #牛舍扩建#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param intervals int整型二维数组 
# @param new_interval int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def insertNewInterval(self , intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
        # write code here
        # 找到位置插入后合并区间
        # 或者直接接到队伍然后重新排一次序
        if len(intervals) == 0:
            return []
        if new_interval == [0,0]:
            return intervals

        # 找到位置，插入区间
        n = len(intervals)
        for i in range(len(intervals)):
            if intervals[i][0] >= new_interval[0]:
                intervals.insert(i, new_interval)
                break
        # 没找到，接到队尾
        if len(intervals) == n:
            intervals.append(new_interval)

        ret = []
        cur = intervals[0]

        for interval in intervals[1:]:
            # 当前区间起始位置小于等于前一个区间结束位置，合并区间
            # 合并后的区间结束位置取当前统计区间与计算区间的最大值
            if interval[0] <= cur[1]:
                cur[1] = max(interval[1], cur[1])
            # 否则断开区间
            else:
                ret.append(cur)
                cur = interval

        ret.append(cur)
        return ret