156MS using std::set, C++, beats 86%


  • -1
    Z

    many edge conditions

    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        struct comp {
            bool operator ()(const Interval &a, const Interval &b) {
                if(a.start==b.start) return a.end<b.end;
                return a.start<b.start;
            }
        };
        set<Interval,comp> Intervals;
        SummaryRanges() {
            
        }
        
        void addNum(int val) {                   
            Interval queryInterval(val,val);
            if(Intervals.size()==0) {
                Intervals.insert(Interval(val,val));
                return;
            }
            Interval ee=*(--Intervals.end());   
            if(val>ee.end) { //judge whether queryInterval is bigger than last Interval
                if(val-1==ee.end) {
                    Intervals.erase(--Intervals.end());
                    Intervals.insert(Interval(ee.start,val));
                }
                else Intervals.insert(Interval(val,val));
                return;
            }
            if(val>=ee.start&&val<=ee.end) return;
            set<Interval,comp>::iterator it=Intervals.lower_bound(queryInterval);
            Interval cur=*it;
            if(val>=cur.start&&val<=cur.end) return;
            if(it==Intervals.begin()) {
                if(val==cur.start-1) {
                    Intervals.erase(Intervals.begin());
                    Intervals.insert(Interval(val,cur.end));
                }
                else Intervals.insert(Interval(val,val));
            }
            else {
                set<Interval,comp>::iterator pre_it=it;
                pre_it--;
                Interval pre=*(pre_it);
                if(val==cur.start-1) {
                    if(val==pre.end+1) {
                        Intervals.insert(Interval(pre.start,cur.end));
                        Intervals.erase(it);
                        Intervals.erase(pre_it);
                    }
                    else {
                        Intervals.insert(Interval(val,cur.end));
                        Intervals.erase(it);
                    }
                }
                else if(val==pre.end+1) {
                    Intervals.insert(Interval(pre.start,val));
                    Intervals.erase(pre_it);
                }
                else if(val>=pre.start&&val<=pre.end) return;//should care this edge case
                else Intervals.insert(Interval(val,val));
            }
            
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> res;
            for(Interval tmp:Intervals) {
                res.push_back(tmp);
            }
            return res;
        }
    };
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * vector<Interval> param_2 = obj.getIntervals();
     */
    

Log in to reply
 

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