Clean C++ Solution with Binary Search to Find the Overlapping Range


  • 2
    A

    The idea is to find the overlapping range, [low, high), with binary search, and then concatenate intervals.begin(), low), mergedInterval, and [high, intervals.end()).

    Time complexity: O(logN) to find the overlapping range. O(n) to copy the intervals.

        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        const int NaN = numeric_limits<int>::max();
        vector<Interval> result;
        
        // Find low interval that overlaps with new interval.
        // i.e. First interval whose end is greater than or equal to newInterval.start.
        // e.g. Given [1,2],[3,5],[6,7],[8,10],[12,16], lower_bound([NaN,4]) returns [3,5].
        Interval lowInterval(NaN, newInterval.start);
        auto low = lower_bound(intervals.begin(), intervals.end(), lowInterval,
                               [](const Interval& l, const Interval& r){ return l.end < r.end; });
        if (low == intervals.end())
        {
            copy(intervals.begin(), intervals.end(), back_insert_iterator<vector<Interval>>(result));
            result.push_back(newInterval);
            return result;
        }
        
        // Find high interval (noninclusive) that overlaps with new interval.
        // i.e. First interval whose start is greater than newInterval.end.
        // e.g. Given [1,2],[3,5],[6,7],[8,10],[12,16], upper_bound([9,NaN]) returns [12,16].
        Interval highInterval(newInterval.end, NaN);
        auto high = upper_bound(intervals.begin(), intervals.end(), highInterval,
                                [](const Interval& l, const Interval& r){ return l.start < r.start; });
        if (high == intervals.begin())
        {
            result.push_back(newInterval);
            copy(intervals.begin(), intervals.end(), back_insert_iterator<vector<Interval>>(result));
            return result;
        }
        
        // Result is [intervals.begin(), low) U mergedInterval U [high, intervals.end()).
        Interval mergedInterval(min(newInterval.start, low->start), max(newInterval.end, (high - 1)->end));
        copy(intervals.begin(), low, back_insert_iterator<vector<Interval>>(result));
        result.push_back(mergedInterval);
        copy(high, intervals.end(), back_insert_iterator<vector<Interval>>(result));
        return result;
    }

  • 0
    R

    O(n) solution, maybe not optimized, just for reference

    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval t) {
            vector<Interval> result; 
            int i=0;
            bool t_added=false;
    	    for(i=0; i<intervals.size(); ++i) {
    		    if(intervals[i].end<t.start)
    			    result.push_back(intervals[i]);
    		    else if(intervals[i].start > t.end){
    			    result.push_back(t);
    			    t_added=true;
    			    break;
    		    }
    		    else { //update t 
    			    t.start=min(t.start, intervals[i].start);
    			    t.end=max(t.end, intervals[i].end);
    		    }
    	    }
    	    if(!t_added) result.push_back(t);
    	    for(; i<intervals.size(); ++i){
    		    result.push_back(intervals[i]);
    	    }
    	    return result;
        }
    };
    

Log in to reply
 

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