Easy to understand in-place binary search solution


  • 0
    Y
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
            int l = 0, r = intervals.size() - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (newInterval.start == intervals[mid].end) {
                    l = mid;
                    break;
                }
                else if (newInterval.start > intervals[mid].end) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            int start = l;
            r = intervals.size() - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (newInterval.end == intervals[mid].start) {
                    r = mid;
                    break;
                }
                else if (newInterval.end > intervals[mid].start) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            int end = r;
            if (start < intervals.size()) {
                newInterval.start = min(newInterval.start, intervals[start].start);
            }
            if (end >= 0) {
                newInterval.end = max(newInterval.end, intervals[end].end);
            }
            intervals.erase(intervals.begin() + start, intervals.begin() + end + 1);
            intervals.insert(intervals.begin() + start, newInterval);
            return intervals;
        }

Log in to reply
 

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