LeetCode 56 合併區間：排序 + 貪心掃描線的經典套路

題目大意

給定一組區間集合，合併所有重疊的區間。
輸入：[[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]

核心思路：排序後單次掃描

1. 按區間起始點 start 升序排序（start 相同時按 end 升序）。
2. 維護當前合併區間 cur，遍歷排序後的列表：

if (interval.start <= cur.end)  // 有重疊
    cur.end = max(cur.end, interval.end);  // 擴展右端點
else  // 無重疊
    ans.push_back(cur);
    cur = interval;

3. 遍歷結束後別忘了把最後一個 cur 加入答案。

C++ 參考實現

vector<Interval> merge(vector<Interval>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start == b.start ? a.end < b.end : a.start < b.start;
    });
    vector<Interval> ans;
    Interval cur = intervals[0];
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].start <= cur.end) {
            cur.end = max(cur.end, intervals[i].end);
        } else {
            ans.push_back(cur);
            cur = intervals[i];
        }
    }
    ans.push_back(cur);
    return ans;
}

複雜度分析

• 時間複雜度：O(n log n)（排序主導）
• 空間複雜度：O(1) 額外空間（不計輸出），或 O(n)（若排序使用額外空間）

常見變體與延伸

• 插入區間（LeetCode 57）：新區間插入已合併列表，同樣先排序或二分查找位置再合併。
• 會議室 II（LeetCode 253）：求同時進行會議的最大數量 → 掃描線 + 差分數組 / 優先隊列。
• 區間交集：雙指針遍歷兩個已合併列表。

避坑清單

1. 輸入為空直接返回空。
2. 排序比較函數必須處理 start 相等的情況，否則 [[1,4],[1,2]] 會合併錯誤。
3. 測試用例：[[1,4],[4,5]] 應合併為 [[1,5]]（端點相接視為重疊）。