C++ solution clean code with STL map O(LogN) on addNum().


  • 0
    S

    Use STL map to store the intervals: map[end]=start. The add() is O(LogN).

    '''
    class SummaryRanges {
    map<int, int> buf;

    public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }

    void addNum(int val) {
        if (buf.empty()) {
            buf[val]=val;
            return;
        }
        
        auto it=buf.lower_bound( val );
        if (it==buf.end()) 
            buf[val]=(buf.count(val-1))?buf[val-1]:val;
        else {
            if (it->second <= val) return;
            if (it->second  == val+1) 
                it->second = (buf.count(val-1))?buf[val-1]:val;
            else 
                buf[val]=(buf.count(val-1))?buf[val-1]:val;
        }
        buf.erase(val-1);
    }
    
    vector<Interval> getIntervals() {
        vector<Interval> res;
        
        for (auto& pr: buf) 
            res.push_back( Interval(pr.second, pr.first) );
        return res;
    }
    

    };
    '''


Log in to reply
 

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