C++ 20 lines follow up using set, and 17 lines using vector


  • 0

    17 lines using vector (about 130ms).
    Inserting/deleting an item in vector takes O(n) time. So this approach gives O(n) for void addNum(int val).
    Also since we could directly return the vector result, vector<Interval> getIntervals() is O(1).

    class SummaryRanges {
    private:
        static bool comp (const Interval& a, const Interval& b) { return a.end < b.start; }     // equal if interleaving
        vector<Interval> container;                                                             // latest result
        
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {}
        
        void addNum(int val) {
            Interval cur = Interval(val, val);
            // locate where to add val
            auto l = lower_bound(container.begin(), container.end(), cur, comp), r = upper_bound(container.begin(), container.end(), cur, comp);                      
            
            if (l-- == r) {                                                             // if val doesn't exist in container
                if (r != container.begin() && (1 + l->end) == val && r != container.end() && (val + 1) == r->start) {
                    l->end = r->end;                                                    // merge container[l] and container[r]
                    container.erase(r);
                } else if (r != container.begin() && (1 + l->end) == val) {
                    l->end = val;                                                       // merge val to container[l]
                } else if (r != container.end() && (val + 1) == r->start) {
                    r->start = val;                                                     // merge val to container[r]
                } else {
                    container.insert(r, cur);                               // insert val between container[l] and container[r]
                }
            }
        }
        
        vector<Interval> getIntervals() {
            return container;
        }
    };
    

    20 lines using set for follow up (roughly the same runtime as above).
    Since there are lots of merges, we want to make void addNum(int val) as fast as possible. In this approach, locating where to add val will take at least O(logn) time, and inserting/deleting an item from a set is O(logn). So each void addNum(int val) takes O(logn) time. As a trade off, vector<Interval> getIntervals() takes O(n) time to construct the result and return it. But since "number of disjoint intervals are small compared to the data stream's size", it's fine.

    class SummaryRanges {
    private:
        struct comp { bool operator() (const Interval& a, const Interval& b) { return a.end < b.start; } }; 
        set<Interval, comp> container;                                                  // equal if interleaving
        
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {}
        
        void addNum(int val) {
            Interval cur = Interval(val, val);
            // locate where to add val
            auto l = container.lower_bound(cur), r = container.upper_bound(cur);
            
            if (l == r) {                                                               // if val doesn't exist in container
                if (r != container.begin() && (1 + (--l)->end) == val && r != container.end() && (val + 1) == r->start) {
                    cur.start = l->start, cur.end = r->end;                             // merge container[l] and container[r]
                    container.erase(l, ++r);
                } else if (r != container.begin() && (1 + l->end) == val) {
                    cur.start = l->start;                                               // merge val to container[l]
                    container.erase(l);
                } else if (r != container.end() && (val + 1) == r->start) {
                    cur.end = r->end;                                                   // merge val to container[r]
                    container.erase(r);
                }                                                       // else insert val between container[l] and container[r]
                container.insert(cur);
            }
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> result;
            for (auto item : container) { result.push_back(item); }                     // construct result
            return result;
        }
    };
    

  • 1
    A

    Hi,

    Your solution looks fancy, but I have a question, why locating where to insert takes only O(logn) in the list version? Searching on a list should takes O(n);

    Thanks.


  • 0

    @aubee
    Good catch. I was not thinking about the lower_bound lib call carefully. Just read this good article and got a better understanding of it: http://www.umich.edu/~eecs381/handouts/binary_search_std_list.pdf
    I've updated my follow up solution using a set instead.


Log in to reply
 

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