leetcode 57. Insert Interval

题目描述

代码：由于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;}
};