Clean c++ solution with comments


  • 0
    N
    class SummaryRanges {
    private:
        map<int, Interval> m;
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            if(m.find(val) != m.end()) return;
            //there will never be key in m that key == val
            //so the iterator is the first key larger than val, or m.end()
            auto larger = m.lower_bound(val); 
            //found a key larger than val, and the interval's start is consecutive to val
            if(larger != m.end() && larger->second.start == val + 1){
                int t = larger->second.end;
                if(larger == m.begin() || ((--larger)->second.end) != val - 1){
                    m[val] = Interval(val, t);
                }else{
                    //the iterator before larger is consecutive to val too, so merge it
                    m[larger->second.start] = Interval(larger->second.start, t);
                }
                m.erase(val+1);
            }else if(larger != m.begin() && ((--larger)->second.end) == val - 1){
                //the iterator before larger is consecutive to val
                larger->second.end = val;
            }else if(larger == m.end() || larger->second.start > val || larger->second.end < val){
                m[val] = Interval(val, val);
            }
            //ignore if the val is already processed
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> v;
            for(auto it=m.begin();it!=m.end();it++){
                v.push_back(it->second);
            }
            return v;
        }
    };
    

Log in to reply
 

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