56. Merge Intervals

📘 題目敘述

給你一個區間陣列 intervals，其中 intervals[i] = [start_i, end_i]。請合併所有重疊的區間，並回傳一個不重疊的區間陣列，且這些區間要能涵蓋輸入中的所有區間。

條件限制

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

🧠 解題思路

這題的核心是：先排序，再線性掃描合併。

我先把 intervals 依照起點排序（sort(intervals.begin(), intervals.end())），排序後有一個很重要的性質：

只要目前掃到的區間起點 i[0] 沒有超過我正在維護的右界 r，就代表它跟目前區間重疊（或相接），可以合併，右界更新成 max(r, i[1])。

如果 i[0] > r，代表它跟目前區間完全不重疊，這時我就把目前 [l, r] 放進答案，然後把新的區間起點終點更新成這個區間。

最後掃完後，還要把最後一段 [l, r] 放進答案。

所有變數

• l：目前正在合併中的區間左界
• r：目前正在合併中的區間右界
• ans：最後回傳的合併後區間列表

🪜 主要流程步驟

1. 先把 intervals 排序

排序後區間會依照起點由小到大排列，這樣我只要往右掃，就能用一個 [l, r] 合併所有重疊區間。

2. 用 l, r 維護當前正在合併的區間

我先用第一個區間初始化：

• l = intervals[0][0]
• r = intervals[0][0]（你的寫法是這樣初始化）

之後每掃到一個區間 i，就根據它的起點決定是否能合併。

3. 如果新的區間起點 > r，代表不重疊，要先結算上一段

當 i[0] > r：

• 代表目前的 [l, r] 已經結束
• 把 [l, r] push 進 ans
• 更新 l = i[0]、r = i[1]，開始合併新的段落

4. 否則代表重疊或相接，更新 r

當 i[0] <= r：

• 代表可以合併
• 我只需要把 r 擴大到 max(r, i[1])

5. 掃完後把最後的 [l, r] 加進答案

因為最後一段不會在迴圈內被推進 ans，所以最後補一行：

ans.push_back({l, r});

⏱️ 複雜度

• 時間複雜度：O(n log n)
  排序花 n log n，掃描合併是 O(n)。
• 空間複雜度：O(n)
ans 最壞可能存下所有區間。

💻 程式碼實作

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int l = intervals[0][0], r = intervals[0][0];
        vector<vector<int>> ans;
        for (auto& i : intervals) {
            if (i[0] > r) {
                ans.push_back({l, r});
                l = i[0];
                r = i[1];
            } else {
                r = max(r, i[1]);
            }
        }
        ans.push_back({l, r});
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/merge-intervals/