Solution For Dummies Like Myself - C++ | 16 ms


  • 1
    P

    At first I struggled with the Big O(n^2) solution but for some reason, the Big O(n log(n)) solution - sorting cost - resonated with me.

    The key is to sort via the start of the interval;
    then you simply check to see if the end of the current interval is greater than the start of the next interval:

    1. If it is not, add it it to the output
    2. If it is, merge by assigning the min start and the max end;
    vector<Interval> merge(vector<Interval>& intervals) { 
    	if(intervals.size() == 0) {
    		return intervals;
    	}
    	
    	//Key to the solution    
    	sort(intervals.begin(), intervals.end(), [] (Interval a, Interval b) {
    		return a.start < b.start;
    	});
    	
    	int i = 0;
    	int j = 1;
    	vector<Interval> result;
    	result.push_back(intervals[0]);
    	
    	while(j < intervals.size()) { 
    		//check for overlap
    		if(result[i].end >= intervals[j].start) { 
    			result[i].start = min(result[i].start, intervals[j].start);
    			result[i].end = max(result[i].end, intervals[j].end); 
    			j++; 
    		} else {  
    			result.push_back(intervals[j]);
    			i++; j++;
    		} 
    	} 
    	
    	return result;
    }
    

Log in to reply
 

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