Simple solution with binary search


  • 0
    R
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        size_t len = intervals.size();
        vector<Interval> res;
        if (!len) return {newInterval};
        auto cmp = [](const Interval& a, const Interval& b){return a.start < b.start;};
        auto it = lower_bound(intervals.begin(), intervals.end(), newInterval, cmp);
        intervals.insert(it, newInterval);
        
        int start = intervals[0].start;
        int end = intervals[0].end;
        for (size_t i = 0; i < intervals.size(); ++i) {
            if (intervals[i].start <= end) {
                end = max(intervals[i].end, end);
            } else {
                res.push_back({start, end});
                start = intervals[i].start;
                end = intervals[i].end;
            }
        }
        res.push_back({start, end});
    
        return res;
    }

Log in to reply
 

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