LeetCode 56 Merge Intervals：排序合並重疊區間

題目大意

給區間列表，合併所有重疊/相鄰區間。例如 [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]。

標準解法：排序 + 線性掃描合並

1. 按區間起點 `start` 升序排序（`start` 相同按 `end` 升序）。
2. 遍歷排序後列表，維護當前合併區間 `cur`。
   - 若 `interval.start <= cur.end`：重疊/相鄰，`cur.end = max(cur.end, interval.end)`。
   - 否則：將 `cur` 加入結果，`cur = interval`。
3. 最後加入 `cur`。

代碼

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

複雜度

• 時間：O(n log n) 排序主導。
• 空間：O(n) 結果存儲（或 O(1) 原地修改）。

失敗嘗試：哈希表法

嘗試開大小為跨度的布爾數組標記覆蓋，但坐標範圍不定，記憶體超限 (MLE)。排序法無此問題。

總結

Merge Intervals 是區間問題的基礎模板：**排序 + 線性合並**。掌握此模板，可解決所有區間合併、插入、交集、並集等變體問題。