Why it is so slow with std::list ?


  • 0
    H

    It takes about 200ms to pass all the tests. I tried to use vector, but it is even worse. Could anyone help me on this?

    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            Interval interval(val, val);
            auto it = lower_bound(lst.begin(), lst.end(), interval,
                [](Interval a, Interval b) {return a.start < b.start;});
            
            if (it == lst.end()) { // empty or val larger than all
                it = lst.insert(it, interval); //insert at end
            }
            else { // val <= it->start
                if (val == it->start) return; // included, all set
                if (val == it->start - 1) { // adjacent to it
                    it->start = val;
                }
                else { // no overlap with current Interval
                    it = lst.insert(it, interval);
                }
            }
            // check if connected to the previous interval
            if (it != lst.begin()) {
                auto pre = prev(it);
                if (it->start <= pre->end + 1) {
                    pre->end = max(it->end, pre->end);
                    lst.erase(it);
                }
            }
        }
        
        vector<Interval> getIntervals() {
            return vector<Interval>(lst.begin(), lst.end());
        }
    private:
        list<Interval> lst;
    };
    

Log in to reply
 

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