Could some one point out why it timeout?


  • 1
    D

    Hey guys,

    I wrote a version that could yield to TLE. Does some one have the same issue?

    Thanks,

    ///===============================

    class SummaryRanges {
    
    public:
    
        /** Initialize your data structure here. */
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            Interval t(val, val);
            auto low = dict.lower_bound(t);
            if (low == dict.end()) {
                dict.insert(Interval(val, val));
            } else {
                int start, end;
                auto p = prev(low);
                if (val+1 == low->start && p != dict.end() && p->end+1 == val) {
                    t.end = low->end, t.start = p->start;
                    dict.erase(low);
                    dict.erase(p);
                    dict.insert(t);
                } else if (val+1 == low->start) { 
                    t.end = low->end, t.start = val;
                    dict.erase(low);
                    dict.insert(t);
                } else if (p != dict.end() && p->end+1 == val) {
                    t.start = p->start, t.end = val;
                    dict.erase(p);
                    dict.insert(t);
                } else {
                    dict.insert(t);
                }
            }
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> res;
            copy(dict.begin(), dict.end(), back_inserter(res));
            return res;
        }
        set<Interval, Interval_compare> dict;
    };

  • 0
    G

    I wrote the same code and got LTE. I don't know why. What I realise is that the last ELSE branch might be the devil. If comment out the last else branch, there is no LTE for the LTE test case. But I don't understand why this happens. I'd like to know the reason, too.

    I'd also like to know why https://leetcode.com/discuss/105790/very-concise-c-solution is not LTE. It shares the same idea but a different implementation. How can it get around LTE?

    BTW, even the following code would LTE:

    void addNum(int val) {
            Interval t(val, val);
            dict.insert(t);
    }
    

    This implies that if there is a test case including a large number of non-consecutive numbers, using set would LTE.


Log in to reply
 

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