Very concise c++ solution.


  • 33
    G

    In general case, vector is OK, it will take O(n) time in each add, and O(1) in get result. But if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size, we'd better use another data structure "set", because the insert operation in vector will cost O(n) time, but it only cost O(log n) in binary search tree, but it will cost O(n) time in getInterval. So use which data structure will depends.

    first one is the solution use vector

    class SummaryRanges {
    public:
        void addNum(int val) {
            auto Cmp = [](Interval a, Interval b) { return a.start < b.start; };
            auto it = lower_bound(vec.begin(), vec.end(), Interval(val, val), Cmp);
            int start = val, end = val;
            if(it != vec.begin() && (it-1)->end+1 >= val) it--;
            while(it != vec.end() && val+1 >= it->start && val-1 <= it->end)
            {
                start = min(start, it->start);
                end = max(end, it->end);
                it = vec.erase(it);
            }
            vec.insert(it,Interval(start, end));
        }
        
        vector<Interval> getIntervals() {
            return vec;
        }
    private:
        vector<Interval> vec;
    };
    

    and below is another solution use binary search tree.

    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        void addNum(int val) {
            auto it = st.lower_bound(Interval(val, val));
            int start = val, end = val;
            if(it != st.begin() && (--it)->end+1 < val) it++;
            while(it != st.end() && val+1 >= it->start && val-1 <= it->end)
            {
                start = min(start, it->start);
                end = max(end, it->end);
                it = st.erase(it);
            }
            st.insert(it,Interval(start, end));
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> result;
            for(auto val: st) result.push_back(val);
            return result;
        }
    private:
        struct Cmp{
            bool operator()(Interval a, Interval b){ return a.start < b.start; }
        };
        set<Interval, Cmp> st;
    };

  • 0
    Z
    This post is deleted!

  • 1
    B

    How should we solve the follow up questions about lots of merges?


  • 0
    G
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 6

    A sample run (insert value 7)

    First, run lower_bound let it point to interval (8,9) because 8 is the first element that is >= 7

    (0,2) (4,6) (8,9) (12,15)    temp = (7, 7)
                 ^
    

    We decrement it because the previous interval can merge 7

    (0,2) (4,6) (8,9) (12,15)    temp = (7, 7)
           ^
    

    Now, it points to the first mergeable interval (if there is one). In this case, (4,6).
    While this interval is mergeable, merge (4,6) with temp to get

    (0,2) (8,9) (12,15)          temp = (4, 7)
           ^
    

    Merge (8,9) with temp to get

    (0,2) (12,15)                temp = (4, 9)
           ^
    

    Can't merge anymore, insert temp

    (0,2) (4,9) (12,15)          temp = (4, 9)
    

    Done.


  • 0
    B

    Really elegant!!!


  • 0
    W

    The most important thing is to define a data structure for interval so that give a number, we can find the interval quickly, and we can add interval to it. std::set can do such operation in O(logN) time.
    Then we needs to define the comparator for interval. A single integer can be regarded as a interval [i,i]. When [i,i] is inside [a,b], we like to define a < operator so that [i,i]==[a,b], which is equivalent to:
    ([i,i] < [a,b]) == false
    ([a,b] < [i,i]) == false
    When this operator is defined, we can easily merge the nearby interval so that the whole series is disjoint.
    For follow-up question, we use a cache vector to hold the result. If the added number can be find in existing interval, the output doesn't need any change.

    class SummaryRanges {
        struct Comp {
            bool operator () (Interval a, Interval b) {
                return a.end<b.start;
            }
        };
        set<Interval, Comp> rbtree_;
        vector<Interval> cache_;
        bool cache_updated_;
    public:
        /** Initialize your data structure here. */
        SummaryRanges(): cache_updated_(true) {
    
        }
    
        void addNum(int val) {
            auto iter = rbtree_.find(Interval(val, val));
            // If there is an existing range covering val
            if (!(iter==rbtree_.end()))
                return;
            // If val can expand any existing range  or even merge two range
            Interval new_interval(val,val);
            auto left = rbtree_.find(Interval(val-1, val-1));
            auto right = rbtree_.find(Interval(val+1, val+1));
            if (!(left==rbtree_.end())) {
                new_interval.start = left->start;
                rbtree_.erase(left);
            }
            if (!(right==rbtree_.end())) {
                new_interval.end = right->end;
                rbtree_.erase(right);
            }
            rbtree_.insert(new_interval);
            cache_updated_ = true;
        }
    
        vector<Interval> getIntervals() {
            if (cache_updated_) {
                cache_updated_ = false;
                cache_ = vector<Interval>(rbtree_.begin(), rbtree_.end());
            }
            return cache_;
        }
    };
    
    

  • 1
    D

    I found it easier to understand if we simplify

    while(it != vec.end() && val+1 >= it->start && val-1 <= it->end)

    to

    while(it != vec.end() && end+1 >= it->start)

    We are basically trying to merge {start, end} with it


  • 0
    1

    I have a question,,
    Since the time complexity of vector.insert is linear..(the memory used by vector is continuous)
    I guess the time complexity of this solution should still be O(n)?


Log in to reply
 

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