concise c++ solution with well explanation,85% beating rate


  • 0
    Z
    class SummaryRanges {
    private:  vector<Interval> sum;
    public:
        SummaryRanges() {}
        void addNum(int val) {
            //Binary searching for the first Interval whose start is bigger than val, i.e. upper_bound(val)
            //if sum is empty or val is smaller than any Interval's start,loops stop at lo=0
            //if val is bigger than any Interval's start,loops stop at lo=sum.size()
            int lo=0,hi=sum.size();
            while(lo<hi){
                int mid=(lo+hi)/2;
                if(sum[mid].start<=val)lo=mid+1;
                else hi=mid;
            }
            //if val is inside any Interval,do nothing;
            //else if val is next to any Interval's start or end, merge it;
            //else insert a new Interval(val,val)
            if(lo==0){
                if(sum.size()&&sum[0].start==val+1)sum[0].start=val;
                else sum.insert(sum.begin(),Interval(val,val)); //is empty or val+1 < sum[0].start
            }
            else if(lo==sum.size()){
                if(val==sum[lo-1].end+1)sum[lo-1].end=val;
                else if(val>sum[lo-1].end+1)sum.push_back(Interval(val,val));
                //val<=sum[lo-1].end return;
            }
            else{  
                if(val<=sum[lo-1].end) return;
                if(sum[lo-1].end+2==sum[lo].start){  
                    sum[lo-1].end=sum[lo].end;
                    sum.erase(sum.begin()+lo);
                }
                else if(val==sum[lo-1].end+1)sum[lo-1].end=val;
                else if(val==sum[lo].start-1)sum[lo].start=val;
                else sum.insert(sum.begin()+lo,Interval(val,val));
            }
        }
        vector<Interval> getIntervals() {
            return sum;
        }
    };
    

Log in to reply
 

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