C++ Short and Easy solution using Two Pointers


  • 0
    X
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            int n = intervals.size(), i = 0, j = n - 1,
                l = newInterval.start, r = newInterval.end;
            //can speed up via binary search
            while (i < n && l > intervals[i].end) ++i;
            while (j >= 0 && r < intervals[j].start) --j;
            if (i <= j) {
                intervals[j].start = min(l, intervals[i].start);
                intervals[j].end   = max(r, intervals[j].end);
                intervals.erase(intervals.begin() + i, intervals.begin() + j);
            } else intervals.insert(intervals.begin() + i, newInterval);
            return intervals;
        }
    };
    

Log in to reply
 

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