C++ 16ms simple solution


  • 0
    X
        class Solution {
        public:
    // oh sorry , it`s not lower_bound. it find the maximum point whose start <= newInterval.end
            int lower_bound(vector<Interval>& intervals, Interval newInterval){
                int left = 0, right = intervals.size() - 1;
                int ans = left;
                while(left <= right){
                    int mid = left + (right -left) / 2;
                    if(newInterval.end >= intervals[mid].start){
                        ans = mid;
                        left = mid + 1;
                        
                    }else{
                        right = mid - 1;
                    }
                }
                return ans;
            }
            vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
                if(intervals.empty()){
                    return vector<Interval>{newInterval};
                }else if(intervals[0].start > newInterval.end){
                    vector<Interval> ans(intervals);
                    ans.insert(ans.begin(), newInterval);
                    return ans;
                }else if(intervals[intervals.size() - 1].end < newInterval.start){
                    vector<Interval> ans(intervals);
                    ans.insert(ans.end(), newInterval);
                    return ans;
                }
                vector<Interval> ans;
                int right = lower_bound(intervals, newInterval);
                int left = 0;
                while(intervals[left].end < newInterval.start){
                    ans.push_back(intervals[left++]);
                }
                Interval tmp;
                tmp.start = newInterval.start < intervals[left].start ? newInterval.start : intervals[left].start;
                tmp.end = newInterval.end > intervals[right].end ? newInterval.end : intervals[right].end;
                ans.push_back(tmp);
                for(int i = right + 1;i < intervals.size(); ++i){
                    ans.push_back(intervals[i]);
                }
                return ans;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.