c++ solution with binary search and merge interval


  • 0
    Y
    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            /* binary search for the insert position */
            auto pos = std::lower_bound(
                intervals.begin(), 
                intervals.end(), 
                newInterval, 
                [](const Interval &lhs, const Interval &rhs) { return lhs.start < rhs.start; }
            );
            intervals.insert(pos, newInterval);
            /* perform merge interval */
            vector<Interval> res = { intervals.front() };
            for (auto &interval : intervals)
            {
                if (interval.start > res.back().end) res.push_back(interval);
                else res.back().end = std::max(res.back().end, interval.end);
            }
            return res;
        }
    };
    

Log in to reply
 

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