題目描述

代碼：由于intervals已經按照左端點排序，并且intervals中的區間全部不重疊，那么可以斷定intervals中所有區間的右端點也已經是有序的。先二分查找intervals中第一個其右端點>=newInterval左端點的區間。然后按照類似于56. Merge Intervals中的方法合并區間。

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> res;int len = intervals.size();if(len == 0){res.push_back(newInterval);return res;}res.reserve(len);//二分查找第一個其右端點>=newInterval左端點的區間int idx = bs(intervals,newInterval[0]);for(int i = 0;i < idx;i++){res.push_back(intervals[i]);}if(idx==len){res.push_back(newInterval);}else{bool to_insert_flag = true;int left = newInterval[0];int right =newInterval[1];if(right<=intervals[idx][1]){if(right<intervals[idx][0]){res.push_back(newInterval);res.push_back(intervals[idx]);}else{left  = min(left,intervals[idx][0]);right = intervals[idx][1];res.push_back({left,right});}idx++;to_insert_flag = false;}else{left = min(left,intervals[idx][0]);idx++;}while(idx < len){if(to_insert_flag){if(right>=intervals[idx][0]){right = max(right,intervals[idx][1]);}else{res.push_back({left,right});res.push_back(intervals[idx]);to_insert_flag = false;}}else{res.push_back(intervals[idx]);}idx++;}if(to_insert_flag){res.push_back({left,right});}}return res;}//二分查找，第一個其右端點>=target的區間int bs(vector<vector<int>>& intervals,int target){int left = 0;int right = intervals.size();int mid = 0;while(left < right){mid = left + ((right-left)>>1);if(intervals[mid][1] >= target){right = mid;}else{left = mid+1;}}return left;}
};

以上做法的時間復雜度是O(logn+n)=O(n)。實際上沒有必要查找。直接一趟遍歷也可以解決。

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> res;int len = intervals.size();res.reserve(len+1);bool to_insert = true;//為true表示新區間還沒有被插入for(int i = 0;i <len;i++){if(to_insert){if(intervals[i][0] > newInterval[1]){//新區間在當前區間的左側，兩者沒有重疊res.push_back(newInterval);res.push_back(intervals[i]);to_insert = false;}else if(intervals[i][1] < newInterval[0]){//新區間在當前區間的右側，兩者沒有重疊res.push_back(intervals[i]);}else{//新區間和當前區間重疊，將它們合并結果作為新的新區間newInterval[0] = min(newInterval[0],intervals[i][0]);newInterval[1] = max(newInterval[1],intervals[i][1]);}}else{res.push_back(intervals[i]);}}if(to_insert)res.push_back(newInterval);return res;}
};

?