LeetCode Merge Intervals：區間合併 — 排序後單次掃描

題目描述

給定一組區間（可能無序），合併所有重疊區間。

範例：

輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]

解題思路

1. 按區間起始點 start 升序排序。
2. 遍歷排序後的區間，維護結果列表 res。
   - 若 res 為空或當前區間 start > res.back().end，無重疊，直接加入。
   - 否則有重疊，更新 res.back().end = max(res.back().end, cur.end)。

參考代碼 (Python)

class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution:
    def merge(self, intervals):
        if not intervals: return []
        intervals.sort(key=lambda x: x.start)
        res = [intervals[0]]
        for cur in intervals[1:]:
            if cur.start <= res[-1].end:
                res[-1].end = max(res[-1].end, cur.end)
            else:
                res.append(cur)
        return res

複雜度分析

• 時間複雜度：O(n log n) —— 排序主導。
• 空間複雜度：O(n) —— 結果列表（不算輸入排序的原地空間）。