12ms in-place C++ solution


  • 0
    C
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            if(intervals.empty())
                return vector<Interval> { newInterval };
            if(newInterval.end < intervals.front().start)
                intervals.insert(intervals.begin(), newInterval);
            else if(newInterval.start > intervals.back().end)
                intervals.push_back(newInterval);
            else
                for(int i = 0; i < intervals.size(); ++i){
                    if(newInterval.start > intervals[i].end && newInterval.end < intervals[i+1].start){
                        intervals.insert(intervals.begin() + i + 1, newInterval);
                        break;
                    }
                    else if(newInterval.start <= intervals[i].end){
                        int cur = i;
                        intervals[cur].start = min(intervals[cur].start, newInterval.start);
                        while(i + 1 < intervals.size() && intervals[i+1].start <= newInterval.end)
                            ++i;
                        intervals[cur].end = max(intervals[i].end, newInterval.end);
                        intervals.erase(intervals.begin() + cur + 1, intervals.begin() + i + 1);
                        break;       
                    }
                    
                   
                }
            return intervals;          
        }
    };
    

Log in to reply
 

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