16ms cpp solution, beats 100%


  • 0
    J
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            vector<Interval> result;
            if(intervals.empty()){
                result.push_back(newInterval);
                return result;
            }
            int size = intervals.size();
            result.reserve(size);
            int i = 0 ;
            //all intervals before newInterval
            while(intervals[i].end<newInterval.start && i < size){
                result.push_back(intervals[i++]);
            }
            if(i == size){
                result.push_back(newInterval);
                return result;
            }
            Interval cur;
            if(newInterval.end<intervals[i].start){ // newInterval doesn't overlap with intervals[i]
                cur = newInterval;
            }else{
                // newInterval overlaps with intervals[i], merge them.
                cur.start = min(newInterval.start, intervals[i].start);
                cur.end = max(newInterval.end, intervals[i].end);
                ++i; //intervals[i] already merged with
            }
            for(; i<size; ++i){
                if(cur.end<intervals[i].start){
                    result.push_back(cur);
                    cur = intervals[i];
                }else {
                    cur.end = max(cur.end, intervals[i].end);
                }
            }
            result.push_back(cur);
            return result;
        }
    };

Log in to reply
 

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