LeetCode 56. Merge Intervals [Medium] [C++] 解題筆記

這題給定一些區間，要求把區域相互重疊的區間合併。

EX:

[1,3],[2,6],[8,10],[15,18]

其中 [1,3],[2,6] 相互重疊，所以需要合併。(剛好 interact 也算重疊,ex: [1,4],[4,5])

Ans: [1,6],[8,10],[15,18]


想法: 
    對於區間(Intervals)相關的問題通常都需要先排序，這題也是一樣，
首先我們先按照每個區間的左端點作升序排序，接著從頭開始遍歷，判斷是否與前一個區間重疊，
若沒有重疊則把前一個區間加入result
(因為已經按照左端點排序，若前一個區間與當前區間沒有重疊表示接下來的區間也不會與該區間重疊)
，而若有重疊則將當前區間與前一個區間合併。


Time Complexity: O(nlogn)

完整程式碼:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) { return {}; }
        auto cmp = [](vector<int>& i1, vector<int>& i2)->bool {
            return i1[0] < i2[0];  
        };
        vector<vector<int>> result;
        vector<bool> merged(intervals.size(), false);
        sort(intervals.begin(), intervals.end(), cmp);
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            auto cur_left = intervals[i][0];
            auto cur_right = intervals[i][1];
            // non-overlap
            if (cur_left > right) {
                vector<int> tmp;
                tmp.emplace_back(left);
                tmp.emplace_back(right);
                result.emplace_back(tmp);
                left = cur_left;
                right = cur_right;
            }
            // overlap merge
            else {
                left = min(left, cur_left);
                right = max(right, cur_right);
            }
        }
        vector<int> tmp;
        tmp.emplace_back(left);
        tmp.emplace_back(right);
        result.emplace_back(tmp);
        
        return result;
    }
};