A 'insert first deal with overlapping later solution'


  • 0
    A

    Really a lazy try, didn't even use binary search to find insert location, surprised it's accepted. But it's pretty easy to understand.
    Basic concept is to insert new interval at index i first, then deal with the potential overlapping with i - 1 and i + 1 if applicable.

    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
    		vector<Interval> returnValue(intervals);
    		if (intervals.empty())
    		{
    			returnValue.push_back(newInterval);
    			return returnValue;
    		}
    		int insertLocation(-1);
    		for(int i = 0; i < intervals.size(); ++ i)
    		{
    			if (intervals[i].start >= newInterval.start)
    			{
    				insertLocation = i;
    				returnValue.insert(returnValue.begin() + i, newInterval);
    				break;
    			}
    		}
    		if (insertLocation == -1)
    		{
    			returnValue.push_back(newInterval);
    			insertLocation = returnValue.size() - 1;
    		}
    		// Handle overlapping
    		handleOverlapping(returnValue, insertLocation);
    
    		return returnValue;
        }
    
    	void handleOverlapping(vector<Interval> & intervals, int index)
    	{
    		// check previous first
    		if (index - 1 >= 0)
    		{
    			if (intervals[index - 1].end >= intervals[index].start)
    			{
    				intervals[index - 1].end = max(intervals[index].end, intervals[index - 1].end);
    				intervals.erase(intervals.begin() + index, intervals.begin() + index + 1);
    				handleOverlapping(intervals, index -1);
    			}
    		}
    		if (index + 1 < intervals.size())
    		{
    			if (intervals[index + 1].start <= intervals[index].end)
    			{
    				if (intervals[index  + 1].end >= intervals[index].end)
    				{
    					intervals[index].end = intervals[index + 1].end;
    				}
    				intervals.erase(intervals.begin() + index + 1, intervals.begin() + index + 2);
    				handleOverlapping(intervals, index);
    			}
    		}
    	}
    };
    

Log in to reply
 

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