Why not use multiset? quite simple

  • 0
    struct comp{
        bool operator()(const Interval& lhs, const Interval& rhs) const {
            return lhs.end<rhs.start;
    typedef multiset<Interval, comp>::iterator IT;
    class Solution {
        multiset<Interval, comp> s;
        vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
            for(int i=0; i<intervals.size(); i++) s.insert(intervals[i]);
            vector<Interval> res;
            pair<IT, IT> p = s.equal_range(newInterval);
            if(p.first==s.end()) s.insert(newInterval);
                int starts=newInterval.start;
                int ends=newInterval.end;
                for(IT it=p.first; it!=p.second; it++){
                    starts=min(starts, it->start);
                    ends=max(ends, it->end);
                s.erase(p.first, p.second);
                s.insert(Interval(starts, ends));
            for(IT it=s.begin(); it!=s.end(); it++) res.push_back(*it);
            return res;

Log in to reply

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