LeetCode 56 Merge Intervals：區間合併排序掃描法

LeetCode 56「Merge Intervals」：給定區間集合，合併所有重疊區間。本文介紹排序 + 掃描線標準解法：按起點排序，線性掃描合併重疊區間。

算法流程

1. 排序：按區間起點 start 升序（起點相同時按終點升序）。
2. 掃描合併：維護結果列表 merged，遍歷排序後區間：
3. 若 merged 為空或當前區間 start > merged.back().end：無重疊，直接加入。
4. 否則：重疊，更新 merged.back().end = max(merged.back().end, cur.end)。

三種重疊情況統一處理

完整代碼（C++）

class Solution {
public:
    vector> merge(vector>& intervals) {
        if (intervals.size() <= 1) return intervals;
        sort(intervals.begin(), intervals.end(),
             [](const vector& a, const vector& b) {
                 return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
             });
        vector> merged;
        for (auto& iv : intervals) {
            if (merged.empty() || iv[0] > merged.back()[1]) {
                merged.push_back(iv);
            } else {
                merged.back()[1] = max(merged.back()[1], iv[1]);
            }
        }
        return merged;
    }
};

Java 版本

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        List merged = new ArrayList<>();
        for (int[] iv : intervals) {
            if (merged.isEmpty() || iv[0] > merged.get(merged.size()-1)[1]) {
                merged.add(iv);
            } else {
                merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], iv[1]);
            }
        }
        return merged.toArray(new int[0][]);
    }
}

複雜度

• 時間：O(n log n) — 排序主導。
• 空間：O(n) — 結果列表（不算輸出空間則 O(1) 或 O(log n) 排序棧）。

關鍵細節

1. 排序關鍵：按 start 升序，start 相同時按 end 升序（保證包含關係正確合併）。
2. 合併條件：iv[0] <= merged.back()[1] 即為重疊（含端點相接）。
3. 邊界情況：空輸入、單區間、全不重疊、全重疊。

變體延伸

• 插入區間 (LeetCode 57)：新區間插入已合併列表，同理定位位置合併。
• 區間交集 (LeetCode 986)：兩列表區間求交集，雙指針掃描。
• 會議室 II (LeetCode 253)：區間重疊深度，掃描線 + 堆/差分數組。

總結

區間合併是「排序 + 貪心掃描」的經典模式。核心洞察：按起點排序後，重疊區間必然連續出現，只需與結果列表末尾比較即可。代碼極短，面試必會。掌握此模板，可秒殺所有區間合併/插入/交集/調度變體題。