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

第五十六題題目：Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

給定一個數組intervals，其中intervals[i] = [starti, endi]，合併所有重疊的區間，並傳回一個不重疊的區間數組，該數組覆蓋所有輸入的區間

解題思路

先把輸入的數組按照starti的大小排序，確保我們在處理時由開頭最小到最大來處理，接著定義
left = intervals[0][0]、right = intervals[0][1]，然後遍歷1~len(intervals)，當遇到right >= intervals[i][0]表示有重疊(例如[1,3]、[2,6]重疊)，那麼把該區間的right更新成右邊界最大的值(變成[1,6])，然後再檢查此區間是否和下一個區間有重疊，有的話一樣作法更新區間，沒有的話則把區間加入到result中，並且將left、right更新成該沒有重疊的區間([1,6]和下一個區間[8,10]不重疊，把[1,6]加入result，並把left更新成8，right更新成10)

程式碼

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals
        intervals.sort(key = lambda x:x[0])
        result = []
        l = intervals[0][0]
        r = intervals[0][1]
        for i in range(1,len(intervals)):
            if r >= intervals[i][0]: #重疊
                r = max(r,intervals[i][1])
            else:
                result.append([l,r])
                l,r = intervals[i]
        result.append([l,r]) #加入最後一組區間
        return result

執行過程

初始狀態

• intervals = [[1,3],[2,6],[8,10],[15,18]]
• result = []
• left = intervals[0][0] = 1
• right = intervals[0][1] = 3

第一次執行(i = 1)

• if right >= intervals[i][0] → 3 >= 2 → True
• right = max(right,intervals[i][1]) = max(3,6) = 6

第二次執行(i = 2)

• if right >= intervals[i][0] → 6 >= 8 → False
• result.append([left,right]) → result.append([1,6]) → result = [[1,6]]
• left,right = intervals[i] = 8,10

第三次執行(i = 3)

• if right >= intervals[i][0] → 10 >= 15 → False
• result.append([left,right]) → result.append([8,10]) → result = [[1,6],[8,10]]
• left,right = intervals[i] = 15,18

跳出迴圈，把最後一組區間加入

• result.append([left,right]) → result.append([15,18]) → result = [[1,6],[8,10],[15,18]]

最後回傳result = [[1,6],[8,10],[15,18]]