合併所有重疊的區間

 

問題描述

給定一組任意順序的時間區間，目標是合併所有重疊的區間，並輸出只包含互不重疊區間的結果。

解決方案

1. 排序區間：首先根據每個區間的起始時間進行排序。這一步可以幫助我們輕鬆識別重疊的區間。

2. 初始化指標：使用 res_idx 來追蹤已合併的區間的最後索引，初始值設為 0。

3. 追踪區間：

   • 遍歷從第二個區間開始的所有區間。
   • 檢查當前區間是否與最後一個合併的區間重疊。
     • 如果重疊，則合併它們，更新結束時間。
     • 如果不重疊，則將當前區間添加到合併列表中，並增加 res_idx。

4. 返回合併後的區間數量：函數返回合併後的區間數量。

實現代碼

以下是 Python 的具體實現：

def merge_overlap(arr):
    if not arr:  # 檢查輸入是否為空
        return 0

    # 步驟 1：根據起始時間對區間進行排序
    arr.sort(key=lambda x: x[0])

    res_idx = 0  # 已合併區間的最後索引

    # 步驟 2：追踪區間
    for i in range(1, len(arr)):
        # 檢查當前區間是否與已合併區間重疊
        if arr[res_idx][1] >= arr[i][0]:
            # 合併重疊的區間
            arr[res_idx][1] = max(arr[res_idx][1], arr[i][1])
        else:
            # 如果不重疊，將當前區間加入合併列表
            res_idx += 1
            arr[res_idx] = arr[i]

    # 返回合併後的區間數量
    return res_idx + 1

# 驅動程式碼
if __name__ == "__main__":
    arr = [[6, 8], [1, 9], [2, 4], [4, 7]]

    # 獲取合併後的區間數量
    new_size = merge_overlap(arr)

    # 打印合併後的區間
    print("合併後的區間為:", end=" ")
    for i in range(new_size):
        print(f"[{arr[i][0]}, {arr[i][1]}]", end=" ")
    print()

測試輸出

對於輸入 arr = [[6, 8], [1, 9], [2, 4], [4, 7]]，執行上述代碼的輸出將是：

合併後的區間為: [1, 9]

總結

• 時間複雜度：排序過程的時間複雜度為 (O(n \log n))，合併過程的時間複雜度為 (O(n))，因此整體時間複雜度為 (O(n \log n))。
• 空間複雜度：使用的是原地合併，因此空間複雜度為 (O(1))。

資料來源：https://www.geeksforgeeks.org/merging-intervals/