56. Merge Intervals

題目網址：https://leetcode.cn/problems/merge-intervals/

題意：給一 array intervals, 其中 intervals[i] = [start_i, end_i], 合併所有重疊的區間, 並返回一個不重疊區間 array。

Solution：

想法：類似 252. Meeting Rooms, 先根據 intervals[i].start 做排序, 若 interval[i].start ≤ res.back().end 的話代表有重疊, 則將當前的 interval.end 設為兩者 end 中較大的（合併）; 若無重疊, 則將 interval[i] 加入到 res 中

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res{intervals[0]}; // 將第一個區間放入到 res

        for (int i = 1; i < intervals.size(); ++i) {
            // 取出當前 interval 的 end
            const int lastEnd = res.back()[1];

            // 若 interval[i].start <= res.back().end, 則重設新的 end (合併)
            // e.g. [[1,4], [2,3]] -> [1,4]
            if (intervals[i][0] <= lastEnd) {
                res.back()[1] = max(lastEnd, intervals[i][1]);
            } else {
                res.emplace_back(intervals[i]);
            }
        }

        return res;
    }
};

• time：$O(n \cdot log(n))$ ➔ sorting
• space：$O(1)$ ➔ 若不考慮要返回 array, 只需常數空間