leetcode 56. Merge Intervals [Medium]

題目敘述

題意很直觀：給定一組區間，把所有重疊的區間合併成一個。

思考

一開始沒想清楚就動手寫了，起初把情況分成三種 case，如下圖所示：

這樣的判斷方式很沒效率。後來想到可以先排序，讓 case B（後者起點小於前者起點）完全消失，大幅簡化主要邏輯。

這是個很值得記住的思路：當發現自己的解法需要同時處理「前後關係不確定」的情況時，先考慮排序能不能解決問題。這題只要按 start 排序，就不會再遇到 case B 的情況。

解題流程

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int length = intervals.size();
        vector<vector<int>> solution;
        sort(intervals.begin(), intervals.end());
        
        int cur = 0;
        while (cur < length) {
            int start = intervals[cur][0];
            int end = intervals[cur][1];
            
            int walker = cur + 1;
            while (walker < length) {
                if (intervals[walker][0] > end) {
                    break;
                }
                
                end = max(end, intervals[walker][1]);
                walker++;
            }
            solution.push_back({start, end});
            cur = walker;
        }
        return solution;
    }
};

這個版本還有改進空間，其實主要邏輯只需要一個 for 迴圈就能完成，速度也更快。不過這裡保留雙層迴圈的寫法，因為比較能直觀地對應到上面的示意圖。