將所有重疊的區間合併為一個，並輸出只包含互不重疊區間的結果

 

問題

給定一組任意順序的時間區間，我們的任務是將所有重疊的區間合併為一個，並輸出只包含互不重疊區間的結果。

解決步驟

1. 排序區間：首先，根據開始時間對區間進行排序，這樣可以更容易地識別重疊的區間。

2. 初始化合併列表：創建一個列表來存儲合併後的區間。

3. 追踪區間：

   • 對於每個當前區間，檢查它是否與合併列表中的最後一個區間重疊。
   • 如果不重疊，則將當前區間添加到合併列表中。
   • 如果重疊，則更新合併列表中最後一個區間的結束時間，將其與當前區間的結束時間取最大值。

4. 返回合併後的列表：最後返回合併後的區間列表。

實作

def merge_intervals(intervals):
    if not intervals:
        return []
    
    # 步驟 1：根據開始時間對區間進行排序
    intervals.sort(key=lambda x: x[0])
    
    # 步驟 2：初始化合併列表
    merged = []
    
    # 步驟 3：追踪區間
    for current in intervals:
        # 如果合併列表為空或沒有重疊，則添加當前區間
        if not merged or merged[-1][1] < current[0]:
            merged.append(current)
        else:
            # 有重疊，合併當前區間
            merged[-1][1] = max(merged[-1][1], current[1])
    
    return merged

# 範例使用
arr1 = [[1, 3], [2, 4], [6, 8], [9, 10]]
arr2 = [[6, 8], [1, 9], [2, 4], [4, 7]]

print(merge_intervals(arr1))  # 輸出: [[1, 4], [6, 8], [9, 10]]
print(merge_intervals(arr2))  # 輸出: [[1, 9]]

代碼解釋

1. 排序：使用 sort 函數根據開始時間對區間進行排序。
2. 合併邏輯：
   • 檢查合併列表是否為空，或合併列表中最後一個區間的結束時間是否小於當前區間的開始時間。
   • 如果有重疊，則更新合併列表中最後一個區間的結束時間為兩個重疊區間的最大結束時間。
3. 輸出：函數返回合併後的區間列表。

時間複雜度

• 排序：(O(n \log n))，其中 (n) 是區間的數量。
• 合併：(O(n))，因為每個區間只處理一次。

因此，整體時間複雜度為 (O(n \log n))，空間複雜度為 (O(n))，用於存儲合併後的區間。

參考資料：https://www.geeksforgeeks.org/merging-intervals/