C++ O(logN) per Add, Clean code with clear logic.


  • 0
    F
    class SummaryRanges {
       map<int, int> starts, ends;
    public:
        SummaryRanges() {}        
        void addNum(int val) {
            auto iter = ends.lower_bound(val);
            if(iter != ends.end() && iter->second <= val )
                return;
            auto iter_l = ends.find(val - 1);
            auto iter_r = starts.find(val + 1);
            if (iter_l != ends.end() && iter_r != starts.end()){
                starts[iter_l -> second] = iter_r->second;
                ends[iter_r -> second] = iter_l -> second;
                ends.erase(iter_l);
                starts.erase(iter_r);
            }else if (iter_l != ends.end()){
                starts[iter_l -> second] = val;
                ends[val] = iter_l->second;
                ends.erase(iter_l);
            }else if (iter_r != starts.end()){
                ends[iter_r -> second] = val;
                starts[val] = iter_r->second;
                starts.erase(iter_r);
            }else{
                starts[val] = val;
                ends[val] = val;
            }
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> result;
            for (auto e : starts)
            {
                result.emplace_back(e.first, e.second );
            }
            return result;
        }
    };

Log in to reply
 

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