C++ solution using binary search, easy to understand


  • 0
    I
    int binary_search(vector<Interval>& intervals, int target) {
        if (intervals.empty()) return -1;
        int low = 0, high = intervals.size() - 1;
        while (low < high) {
            int mid = (low + high) >> 1;
            if (target > intervals[mid].start) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return intervals[low].start <= target ? low : low - 1; 
    }
    
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> ret;
        int i1 = binary_search(intervals, newInterval.start), 
            i2 = binary_search(intervals, newInterval.end);
        int c = ((i1 == -1 || newInterval.start > intervals[i1].end) ? 0 : 1) +
            ((i2 == -1 || newInterval.end > intervals[i2].end) ? 0 : 2);
        for (int i = 0; i <= i1; i++) {
            ret.push_back(intervals[i]);
        }
        switch (c) {
            case 0:
                ret.push_back(newInterval);
                break;
            case 1:
                ret.back().end = newInterval.end;
                break;
            case 2:
                ret.emplace(ret.end(), newInterval.start, intervals[i2].end);
                break;
            case 3:
                ret.back().end = intervals[i2].end;
                break;
        }
        for (int i = i2 + 1; i < intervals.size(); i++) {
            ret.push_back(intervals[i]);
        }
        return ret;
    }

Log in to reply
 

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