題目

56. Merge Intervals 給定一個區間陣列intervals(List[List[int]])，其中 intervals[i] = [start_i, end_i]，合併所有重疊區間，並返回覆蓋輸入中所有區間的非重疊區間陣列。

例子 1:

區間陣列: intervals = [[1,3],[2,6],[8,10],[15,18]]

由於區間 [1,3] 與 [2,6] 重疊, 將這兩個區間合併，區間為 [1,6]。其餘區間都沒有重疊，就直接保留。

合併重疊區間後的陣列為: [[1,6],[8,10],[15,18]]

解題思路

要把所有重疊的區間合併起來，合併成一個新的區間，最後返回一個不重疊的區間陣列ans。

先把輸入的區間按照開始時間排序，這樣才能保證我們遍歷到的區間是按照時間順序來的。
定義一個新的答案陣列ans，將第一個區間加入答案陣列ans裡。
然後從第二個區間開始遍歷輸入的區間陣列intervals。 3.1 如果遍歷到的這個區間[start_i, end_i]和答案陣列ans中最後一個區間[start_last, end_last]有重疊，那就合併這兩個區間。 判斷是否重疊(判斷區間[start_i, end_i]與答案陣列ans中最後一個區間[start_last, end_last]是否重疊): 由於輸入的區間是按照時間序被排序過的，因此答案陣列中的每個區間的開始時間都不晚於現在遍歷到的區間，(start_i>=start_last)，而且每個區間的end都比start晚，因此如果start_i<end_last，則代表兩個區間重疊。 合併區間: 把答案陣列ans中最後一個區間的結束時間end_last更新為兩個區間結束時間的最大值(max(end_last, end_i))。 3.2 如果沒有重疊，就把這個區間加入答案陣列ans。
遍歷結束後，返回答案陣列ans。

實作

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []

        for interval in intervals:
            if not ans or interval[0] > ans[-1][1]:
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
                
        return ans