Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

題目大意：
給出一個(gè)二元組構(gòu)成的區(qū)間數(shù)組, 在其中插入一個(gè)新的區(qū)間, 使得新的區(qū)間插入后, 數(shù)組也應(yīng)當(dāng)滿足嚴(yán)格升序并且區(qū)間之間沒(méi)有重疊.

解題思路：
若將新區(qū)間直接插入到區(qū)間數(shù)組中就是第56題的合并區(qū)間的題目，解題思路如下：http://www.itdecent.cn/p/67935d04b104

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        
        intervals.append(newInterval)
        intervals.sort()
        if len(intervals) == 1:
            return intervals
        res = []
        for i in range(len(intervals)):
            if res == []:
                res.append(intervals[i])
            else:
                if intervals[i][0] <= res[-1][1]:
                    res[-1][1] = max(intervals[i][1], res[-1][1])
                else:
                    res.append(intervals[i])
        return res

其他思路分區(qū)間討論

• 不重疊部分
• intervals[i]右邊小于newInterval左邊，將intervals[i]置左
• newInterval右邊小于intervals[i]左邊，將intervals[i]置右
• 重疊部分
• 將中間重疊區(qū)間合并

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [newInterval]
        left = []
        right = []
        l = newInterval[0]
        r = newInterval[1]
        for i in range(len(intervals)):
            if intervals[i][1] < newInterval[0]:
                left.append(intervals[i])
            elif newInterval[1] < intervals[i][0]:
                right.append(intervals[i])
            else:
                l = min(intervals[i][0], newInterval[0], l)
                r = max(intervals[i][1], newInterval[1], r)
        return left + [[l, r]] + right

參考：https://blog.csdn.net/Wayne_Mai/article/details/80289874

解該題過(guò)程中遇到的問(wèn)題及python誤區(qū)：http://www.itdecent.cn/p/eee82a92fe43