C++ code use binary search


  • 2
    Z
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        if(intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
        
        int first=0, piv=0, count=intervals.size(), step = 0;
        while(count > 0) {  // lower bound of ends
            step = count/2; piv = first + step;
            if(intervals[piv].end < newInterval.start) {
                first = ++piv;
                count -= step + 1;
            } else count = step;
        }
        
        int last = first;
        count = intervals.size() - first;
        while(count > 0) {  // upper bound of starts
            step = count/2; piv = last + step;
            if(intervals[piv].start <= newInterval.end) {
                last = ++piv;
                count -= step + 1;
            } else count = step;
        }
        
        if(last == first)
            intervals.insert(intervals.begin()+first, newInterval);
        else {
            intervals[first].start = min(newInterval.start, intervals[first].start);
            intervals[first].end   = max(newInterval.end,   intervals[last-1].end);
            intervals.erase(intervals.begin()+(first+1), intervals.begin()+last);
        }
        
        return intervals;
    }

  • 0
    I

    Just wanted to say that your solution is the most elegant solution I have seen for this question. It's amazing that this can implicitly handle all the edge cases.


Log in to reply
 

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