My easy C++ solution


  • 1
    T
     //smart solution by myself
    class Solution {
    public:
    	vector<Interval> insert(vector<Interval>& intervals,Interval newInterval)
    	{
    	    //use two pointer to locate the left and right
    		int left=0,right=intervals.size();
    		for(int i=0;i<intervals.size();i++)
    			if(newInterval.start>intervals[i].end)
    				left=i+1;
    		for(int i=intervals.size()-1;i>=0;i--)
    			if(newInterval.end<intervals[i].start)
    				right=i;   //the right is the one after the last one
    				
            //if the new interval is in the head,then insert as new head
    		if(right==0)
    		{
    			intervals.insert(intervals.begin(),newInterval);
    			return intervals;
    		}
            //if the new interval is in the tail,then insert as new tail 
    		if(left==intervals.size())
    		{
    			intervals.insert(intervals.end(),newInterval);
    			return intervals;
    		}
            //construct the newinterval
    		newInterval.start=min(newInterval.start,intervals[left].start);
    		newInterval.end=max(newInterval.end,intervals[right-1].end);
    		
            //firt erase the old intervals,then insert one new interval
    		intervals.erase(intervals.begin()+left,intervals.begin()+right);
    		intervals.insert(intervals.begin()+left,newInterval);
    
    		return intervals;
    	}
    };

Log in to reply
 

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