leetcode 56. Merge Intervals [Medium]

2021-12-24 92 words One minute

Contents

題目敘述

這題的題目本身意思很直觀，給很多 區間，然後將所有範圍重疊的 區間 合併。

思考

一開始在看到題目的時候沒有想清楚就開始寫了，起初的想法是把 case 分成三種，如下圖所示

這樣判斷起來很沒有效率，後來才想到可以利用排序的方式，來讓所有的 case B 都消失，簡化主要邏輯判斷。如果在寫題目的過程中，發現自己的寫法可能遇到物件出現在前後的 case，必須要先思考看看是否能透過排序來解決，在這題中，透過排序可以讓每個分段都按照 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 迴圈就能解決了，速度也比較快，但是紀錄這個版本的解答是因為這段 code 可以比較直觀的想像出上面的示意圖。