因為 intervals 已經是 sorted,所以我們可以排除掉 end 比 newInterval.start 還要早的所有 interval,然後遇到第一個 end 比 newInterval.start 早的 interval,我們就可以開始 merge。
下面的說明很好地總結了幾種 overlap 的形式:
程式碼如下:
classSolution {public:vector<vector<int>> insert(vector<vector<int>>& intervals,vector<int>& newInterval) {int i =0; // Skipping all intervals which ends before newInterval starts vector<vector<int>> res;while(i <intervals.size() &&intervals[i][1] <newInterval[0]) {res.push_back(intervals[i]);++i; } // Keep merging until intervals[i] starts after newInterval while(i <intervals.size() &&intervals[i][0] <=newInterval[1]) {newInterval[0] =min(newInterval[0],intervals[i][0]);newInterval[1] =max(newInterval[1],intervals[i][1]);++i; }res.push_back(newInterval); // Push all left interwhile(i <intervals.size()) {res.push_back(intervals[i]);++i; }return res; }};
Runtime: 16 ms, faster than 82.65% of C++ online submissions for Insert Interval. Memory Usage: 12.2 MB, less than 100.00% of C++ online submissions for Insert Interval.