leetcode : Insert Interval

runtime 13 ms, beats 95.58% of cpp submissions
O(n) solution with explanation

tags: None

🔗 link

Insert Interval

📖 description

給定一個 sorted 區間陣列 intervals，以及一個需要新增的區間 newInterval，請求將區間放進 intervals ，並保持 intervals 仍然是已排序的。

ex.
    Input: 
        intervals = [[1,3],[6,9]], newInterval = [2,5]
    Output: 
        [[1,5],[6,9]]

    注意可能會出現需要合併區間的情形

🧠 solution

當看見給定的輸入是一個 sorted array ，可能會很直覺的認為本題需要使用 binary search ，但由於需要新增資料到陣列中，因此最差時間複雜度一定會被限制在 O(n) ，所以使用 linear search 反而能避免在搜尋時出現的一些處理問題。

在做 linear search 時，新區間相對於當前區間共有 3 種情形。

• 區間 n 在當前區間的 前 方，複製當前區間
• 區間 n 在當前區間的 後 方，複製區間 n ，並在後方複製剩下的區間，回傳
• 區間 n 與當前區間有重疊，將 n 的上下限更新 (維護重疊的最大區間)

而如果沒有位置把 n 新增進陣列中，代表 n 應該放在最後

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& in, vector<int>& n) {
        vector<vector<int>> ans;
        for(int i=0;i<in.size();i++){
            if(in[i][1]<n[0]){               // 如果區間 n 在當前區間的後方
                ans.emplace_back(in[i]);
            }
            else if(n[1]<in[i][0]){         // 如果需要新增的區間在當前區間的前方
                                            // 則後方區間可直接複製並回傳
                ans.emplace_back(n);
                ans.insert(ans.end(),in.begin()+i,in.end());
                return ans;
            }
            else{                           // 出現需要合併區間的情況
                                            // 讓區間 n 維持被合併的下限及上限
                n[0] = min(n[0],in[i][0]);
                n[1] = max(n[1],in[i][1]);
            }
        }
        ans.emplace_back(n);                // 區間出現在結尾
        return ans;
    }
};