C++ solution using STL and iterator

  • 0
    bool operator<(const Interval& lhs, const Interval& rhs) {
        return lhs.start < rhs.start;
    class Solution {
        vector<Interval> insert(vector<Interval>& a, Interval x)
            vector<Interval> ret;
            Interval y {x.end, x.end};
            auto beg = a.begin(), end = a.end();
            auto lo = lower_bound(beg, end, x);
            auto hi = upper_bound(beg, end, y);
            ret.insert(ret.end(), beg, lo);
            auto max_end = max_element(lo, hi, [](Interval lhs, Interval rhs){
                                           return lhs.end < rhs.end;});
            if (max_end != hi && x.end < max_end->end)
                x.end = max_end->end;
            if (!ret.empty()) {
                auto &back = ret.back();
                if (back.end >= x.start)
                    back.end = max(back.end, x.end);
            else ret.push_back(x);
            ret.insert(ret.end(), hi, end);
            return ret;

Log in to reply

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