C++ solution using STL and iterator


  • 0
    G
    bool operator<(const Interval& lhs, const Interval& rhs) {
        return lhs.start < rhs.start;
    }
    
    class Solution {
    public:
        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);
            }
            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.