Simple C++ solution using vector with explanations


  • 0
    A
    class SummaryRanges {
        vector<Interval> _data;
    public:
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            if (_data.empty()) { _data.push_back(Interval(val, val)); return; }
            
            // find first interval which start is greater or equal to val
            auto cmp = [](Interval a, Interval b) { return a.start < b.start; };
            auto it = lower_bound(_data.begin(), _data.end(), Interval(val, val), cmp);
            
            // we are only interested in found interval or one before it
            // name them a and b. If it points to either begin or end of _data a and b will be the same
            auto a = it == _data.begin() ? it : it - 1;
            auto b = it == _data.end() ? it - 1 : it;
    
            // if val is already there it must be in a or b. Nothing to do in that case
            if (a->start <= val && a->end >= val) return;
            if (b->start <= val && b->end >= val) return;
    
            // val extends both intervals and they need to be merged
            if (a->end + 1 == val && b->start - 1 == val) {
                a->end = b->end;
                _data.erase(b);
                return;
            }
            
            // val extends a
            if (a->end + 1 == val) { a->end = val; return; }
            
            // val extends b
            if (b->start - 1 == val) { b->start = val; return;}
            
            // val extends no intervals in _data. Insert a new one
            _data.insert(it, Interval(val, val));
        }
        
        vector<Interval> getIntervals() {
            return _data;
        }
    };
    

  • 0
    S

    excellent, it's brilliant


Log in to reply
 

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