[C++] My binary-search solution


  • 0
    J
    1. Find the range of the intervals that will be merged.
    2. Merge intervals and insert the new interval.

    That's all. Please see my comment in the code:

    class Solution {
    public:
        vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
            vector<Interval> result;
            // the range of the intervals that will be merged
            int ldx = -1;                // lower bound
            int rdx = intervals.size();  // upper bound
            // binary search for ldx
            {
                int left = 0;
                int right = intervals.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    Interval interval = intervals[mid];
                    if (newInterval.start < interval.start) {
                        right = mid;
                    } else if (newInterval.start > interval.end) {
                        ldx = mid + 1;
                        left = mid + 1;
                    } else {
                        ldx = mid;
                        break;
                    }
                }
                // if newInterval.start is bigger than all intervals[i].end
                if (ldx >= 0 && ldx >= intervals.size()) {
                    result.reserve(intervals.size() + 1);
                    result.insert(result.end(), intervals.begin(), intervals.end());
                    result.push_back(newInterval);
                    return result;
                }
            }
            // binary search for rdx
            {
                int left = 0;
                int right = intervals.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    Interval interval = intervals[mid];
                    if (newInterval.end < interval.start) {
                        rdx = mid - 1;
                        right = mid;
                    } else if (newInterval.end > interval.end) {
                        left = mid + 1;
                    } else {
                        rdx = mid;
                        break;
                    }
                }
                // if newInterval.end is smaller than all intervals[i].start
                if (rdx < 0) {
                    result.reserve(intervals.size() + 1);
                    result.push_back(newInterval);
                    result.insert(result.end(), intervals.begin(), intervals.end());
                    return result;
                }
            }
            // merge and insert (ldx <= rdx)
            if (ldx >= 0 && intervals[ldx].start < newInterval.start) {
                newInterval.start = intervals[ldx].start;
            }
            if (rdx < intervals.size() && intervals[rdx].end > newInterval.end) {
                newInterval.end = intervals[rdx].end;
            }
            result.reserve(intervals.size() - (rdx - ldx) + 1);
            if (ldx >= 0) {
                result.insert(result.end(), intervals.begin(), intervals.begin() + ldx);
            }
            result.push_back(newInterval);
            if (rdx < intervals.size()) {
                result.insert(result.end(), intervals.begin() + rdx + 1, intervals.end());
            }
            return result;
        }
    };

Log in to reply
 

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