C++_Time: O(n)_Space: O(1)_16ms(52.69%)


  • 0
      class Solution {
      public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        if(intervals.size() < 1){res.push_back(newInterval); return res;}
        
        int i = 0;
        int k = 1;// to judge whether the newInterval has been already in the vector
        
        while(i < intervals.size()){
            if(intervals[i].end < newInterval.start){res.push_back(intervals[i]); i++; continue; }
            else if(intervals[i].start > newInterval.end){
                if(k){res.push_back(newInterval);k = 0;} res.push_back(intervals[i]); i++; continue;}
            
            int b = max(newInterval.end,intervals[i].end) ;
            int a = min(intervals[i].start, newInterval.start);
            int j = i+1;
            while(j < intervals.size() && intervals[j].start <= b){
                b = max(intervals[j].end, b);
                j++;
            }
            intervals[i].end = b;
            intervals[i].start = a;
            res.push_back(intervals[i]);
            i = j;
            k = 0;
        }
        
        if(k){
            res.push_back(newInterval);
        }
        return res;
    }      };

Log in to reply
 

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