今天是紀錄LeetCode解題的第五十七天

第五十七題題目：You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

給定一個不重疊的區間數組intervals，其中intervals[i] = [starti, endi]，starti、endi分別表示區間的開始和結束，並按starti升序排列，同時給定另一個新的區間newInterval，將新區間插入到intervals裡，intervals仍然按升序排列並且沒有任何重疊區間(如有必要，合併重疊區間)

注意：無須將intervals就地更改(in-place)，可以建立新的數組並返回它

解題思路

將intervals的區間一一取出判斷，如果原本的區間在新區間的左邊，則直接將它加入到結果中，如果在右邊，則將新區間加入到結果中，並把新區間更改成原區間，如果原區間和新區間重疊，則把新區間更改成這兩段區間的最小值到最大值當作新區間

程式碼

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        for interval in intervals:
            #原區間在新區間的左邊
            if interval[1] < newInterval[0]:
                res.append(interval)
            #原區間在新區間的右邊
            elif interval[0] > newInterval[1]:
                res.append(newInterval)
                newInterval = interval
            else:
                #重疊
                newInterval[0] = min(newInterval[0], interval[0])
                newInterval[1] = max(newInterval[1], ) #後面參數是interval[1]，顯示不出來
        res.append(newInterval)
        return res

執行過程