56. 合并區間

1. 排序：
   • 將所有區間按起始位置?start?從小到大排序。
   • 這樣，重疊的區間會相鄰排列，方便后續合并。
2. 合并：
   • 初始化一個空列表?merged，用于存儲合并后的區間。
   • 遍歷排序后的區間列表：
     • 如果?merged?為空，或者當前區間與?merged?中最后一個區間不重疊，則將當前區間直接添加到?merged?中。
     • 否則，合并當前區間與?merged?中最后一個區間，更新?merged[-1][1]?為兩者結束位置的最大值。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:# 1. 按照區間的起始位置進行排序intervals.sort(key=lambda x: x[0])# 2. 初始化一個空列表用于存儲合并后的區間merged = []# 3. 遍歷排序后的區間列表for interval in intervals:# 如果 merged 為空，或者當前區間與 merged 中最后一個區間不重疊if not merged or merged[-1][1] < interval[0]:# 將當前區間直接添加到 merged 中merged.append(interval)else:# 否則，合并當前區間與 merged 中最后一個區間merged[-1][1] = max(merged[-1][1], interval[1])# 4. 返回合并后的區間列表return merged

時間復雜度分析

1. 排序：時間復雜度為?O(n log n)，其中?n?是區間的數量。
2. 遍歷合并：時間復雜度為?O(n)。

• 總時間復雜度為?O(n log n)。

?空間復雜度分析

• 使用了額外的列表?merged?存儲結果，空間復雜度為?O(n)。