leetcode : Merge Intervals

runtime 39 ms, beats 94.21% of cpp submissions
nlog(n) solution with explanation

tags: sorting

🔗 link

Merge Intervals

📖 description

給定一個陣列，陣列內的每個元素都是一個區間 (包含區間的上下限) ，要求把陣列內有重疊的區間組合成同一個區間。

ex.
    Input: 
        intervals = [[1,3],[2,6],[8,10],[15,18]]

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

    Explanation: 
        Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

🧠 solution

在考慮如何解題之前，要先理解要怎麼判斷兩個區間是可以合成的

ex.
    [1,3], [2,6] 是兩個可以合成的區間
    因為 2 < 3 ，表示他們是有重疊的

    [1,4], [2,3] 也是兩個可以合成的區間
    而且第一個區間完美包括了第二個區間 (該區間的上限要取最大值)

考慮完怎麼合成區間，還要考慮到輸入的區間是未經排序的，也就是兩個可能重疊的區間不會被放在連續的位置，所以我們必須排序一次輸入。

⏳ time complexity

排序輸入 O(nlog(n)) ，遍歷資料 *O(n)*，總時間複雜度 O(nlog(n))
總時間複雜度 O(nlog(n))

📝 code

bool cmp(vector<int>& a,vector<int>& b){
    if(a[0]==b[0]){     
        return a[1]<b[1];
    }
    else{
        return a[0]<b[0]; // 回傳下限較低的區間
    }
}
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& inter) {
        vector<vector<int>> ans;
        sort(inter.begin(),inter.end(),cmp);
        for(int i=0;i<inter.size();i++){
            if(ans.empty() || ans.back()[1]<inter[i][0]){   // 如果當前陣列是空的或無法合成
                ans.emplace_back(inter[i]);
            }
            else{
                ans.back()[1] = max(ans.back()[1],inter[i][1]); // 如果可以合成，更新上限為較大的
            }
        }
        return ans;
    }
};