C++ solution using std::set


  • 1
    P

    Using std::set (implemented with red-black tree generally), for every update (insertion), the time cost is O(lgn).

    bool operator < (const Interval &i1, const Interval &i2) {
        return i1.start < i2.start;
    }
    
    void update_end(const Interval &i, int end) {
        const_cast<Interval &>(i).end = end;
    }
    
    class SummaryRanges {
        set<Interval> data;
    
    public:
        SummaryRanges() {}
    
        void addNum(int val) {
            Interval i(val, val);
    
            auto &&next = upper_bound(data.begin(), data.end(), i);
    
            if (next != data.begin() && next != data.end()) {
                auto prev = next; --prev;
    
                if (prev->end >= val) {
                    return;
                }
            }
    
            if (next == data.end() && !data.empty()) {
                if (data.rbegin()->end >= val) {
                    return;
                }
            }
    
            auto &&curr = data.insert(next, i);
            auto prev = data.end();
    
            bool erase_curr = false, erase_next = false;
    
            if (curr != data.begin()) {
                prev = curr; --prev;
    
                if (prev->end == curr->start - 1) {
                    update_end(*prev, curr->start);
                    erase_curr = true;
                }
            }
    
            if (next != data.end()) {
                if (next->start == curr->start + 1) {
                    if (erase_curr) {
                        update_end(*prev, next->end);
                    } else {
                        update_end(*curr, next->end);
                    }
    
                    erase_next = true;
                }
            }
    
            if (erase_curr) {
                data.erase(curr);
            }
    
            if (erase_next) {
                data.erase(next);
            }
        }
    
        vector<Interval> getIntervals() {
            return vector<Interval>(data.begin(), data.end());
        }
    };

  • 1
    S

    Nice!

    I wrote a similar solution here. For an unknown reason, my solution got a "memory limit exceeded" verdict. If you have hints why, I'd be thankful.

    I'm curious about your use of upper_bound. Shouldn't you use the specialized method for sets (i.e., data.upper_bound(...)?

    You could avoid the const_cast. To do that, remove the old element from the set and create a new one.

    Overall, I really like your code!


  • 0
    D

    @Sjlver I use set too, and get MLE as well. I don't know why either. It should be O(N) space.


Log in to reply
 

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