LeetCode 56 Merge Intervals：排序 + 貪心合併區間 (O(n log n))

問題

給定區間集合，合併所有重疊區間。例 [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]。

排序貪心法

1. 按區間起點 start 升序排序 (起點相同時按終點升序)。
2. 遍歷排序後列表，維護當前合併區間 cur：
- 若 interval.start <= cur.end：重疊，cur.end = max(cur.end, interval.end)。
- 否則：將 cur 加入答案，cur = interval。
3. 循環結束別忘記加入最後一個 cur。

Java 實現

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (a,b) -> a[0]-b[0]);
        List res = new ArrayList<>();
        int[] cur = intervals[0];
        for (int i=1; i

C++ 實現
vector> merge(vector>& a) {
    if (a.empty()) return {};
    sort(a.begin(), a.end());
    vector> res;
    res.push_back(a[0]);
    for (int i=1;i

複雜度
時間 O(n log n) (排序主導)，空間 O(n) (結果 + 排序棧)。