LeetCode如何合并區間

# LeetCode如何合并區間

## 引言

在算法面試和編程競賽中，區間合并（Merge Intervals）是一個經典且高頻出現的問題。LeetCode上的第56題"合并區間"要求我們將所有重疊的區間合并，并返回一個不重疊的區間數組。本文將深入探討這個問題，從基礎概念到多種解法，最后給出優化技巧和實際應用場景。

## 問題描述

給定一個區間集合 `intervals`，其中 `intervals[i] = [starti, endi]`。合并所有重疊的區間，并返回一個不重疊的區間數組，該數組需覆蓋輸入中的所有區間。

**示例1：**

輸入: intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出: [[1,6],[8,10],[15,18]] 解釋: 區間 [1,3] 和 [2,6] 重疊, 合并為 [1,6]

**示例2：**

輸入: intervals = [[1,4],[4,5]] 輸出: [[1,5]] 解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間

## 解題思路

### 關鍵觀察
1. **區間重疊的條件**：當兩個區間A和B滿足`A[1] >= B[0]`時，它們可能重疊（注意需要具體比較）
2. **合并后的區間**：合并后的新區間的起始點是兩個區間中較小的`start`，結束點是較大的`end`

### 基本步驟
1. 將區間按起始點排序
2. 初始化結果列表，放入第一個區間
3. 遍歷后續每個區間：
   - 如果當前區間與結果列表中最后一個區間重疊，則合并
   - 否則直接加入結果列表

## 代碼實現

### Python解法
```python
def merge(intervals):
    if not intervals:
        return []
    
    # 按區間起始點排序
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:  # 有重疊
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    return merged

Java解法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // 按區間起始點排序
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> result = new ArrayList<>();
    int[] newInterval = intervals[0];
    result.add(newInterval);
    
    for (int[] interval : intervals) {
        if (interval[0] <= newInterval[1]) {
            newInterval[1] = Math.max(newInterval[1], interval[1]);
        } else {
            newInterval = interval;
            result.add(newInterval);
        }
    }
    
    return result.toArray(new int[result.size()][]);
}

復雜度分析

• 時間復雜度：O(n log n)，主要來自排序操作
• 空間復雜度：O(log n)（排序所需的?？臻g）或 O(n)（存儲結果所需空間）

邊界情況處理

實際編碼時需要特別注意以下邊界情況： 1. 空輸入：intervals = [] 2. 單個區間：intervals = [[1,3]] 3. 完全包含的區間：[[1,4],[2,3]] → [[1,4]] 4. 不相鄰但值相同的區間：[[1,4],[5,6]]不應合并

算法優化

不需要顯式合并的寫法

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

處理大數區間

當區間值非常大時（如達到2^31），可以考慮： 1. 使用長整型存儲 2. 分治策略處理超大數據集

變種問題

1. 插入區間（LeetCode 57）

給定一組不重疊的區間和一個新區間，插入并合并

解法：先插入再合并，或直接遍歷處理

2. 會議室II（LeetCode 253）

計算需要的最少會議室數量

解法：使用最小堆或時間點排序

3. 區間交集（LeetCode 986）

給定兩個區間列表，找出它們的交集

解法：雙指針遍歷

實際應用場景

1. 日程安排系統：合并用戶的可工作時間段
2. 基因序列比對：合并重疊的基因片段
3. 磁盤空間管理：合并相鄰的可用空間塊
4. 交通調度系統：合并車輛運行時間重疊段

常見錯誤與調試技巧

常見錯誤

1. 忘記先排序區間
2. 合并時只更新end值而忘記比較max
3. 處理最后一個區間時的邊界條件

調試方法

1. 打印每次合并前后的區間狀態
2. 使用可視化工具繪制區間圖
3. 構造小型測試用例驗證

擴展思考

1. 如果區間是開區間（如(1,3)）該如何處理？
2. 如何并行化處理超大規模的區間合并？
3. 如何實時處理動態變化的區間流數據？

總結

區間合并問題通過排序+線性掃描的解法，展示了算法設計中”預處理+貪心”的經典模式。掌握這個問題不僅能幫助我們解決LeetCode上的類似題目，更能培養處理實際工程中重疊范圍類問題的思維能力。建議讀者在理解基礎解法后，嘗試解決前文提到的各種變種問題，以深化對這一模式的理解。

參考資料

1. LeetCode官方題解 2.《算法導論》分治策略相關章節
2. 編程競賽中的經典區間處理技巧

”`

注：本文實際字數約1800字，可根據需要補充更多實現細節或應用案例以達到精確字數要求。