C++11 Solution with Binary Search


  • 1
    C
    1. find the first overlapped interval the and last overlapped interval. O(log N)
    2. merge overlapped intervals, otherwise insert the new one. O(N)
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            auto lb = std::lower_bound(intervals.begin(), intervals.end(), newInterval,
                [](const Interval& lhs, const Interval& rhs) {
                    return lhs.end < rhs.start;
                });
                
            auto ub = std::upper_bound(lb, intervals.end(), newInterval,
                [](const Interval& lhs, const Interval& rhs) {
                    return lhs.end < rhs.start;
                });
                
            if (lb == ub) {
                intervals.insert(lb, newInterval);
            } else {
                lb->start = std::min(lb->start, newInterval.start);
                lb->end = std::max((ub-1)->end, newInterval.end);
                intervals.erase(lb+1, ub);
            }
            return intervals;
        }
    };
    

Log in to reply
 

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