Easy to understand C++ solution, O(1) for add and O(m) for get, where 'm' is the size of numbers added after last get.


  • 0
    B

    General idea:

    Each time calling addNum, I push the new number into mVals.

    Each time calling getIntervals, I add the new numbers in mVals to mInts. Delete all the members in mVals since we already constructed them in mVals and there is no need to construct next time calling getIntervals.

    How to construct:

    Go through existing mInts and find the position of each number i in mVals.

    (1) i < start - 1: Add new Interval in front.

    (2) i == start - 1: Use i as the start

    (3) i within the interval: do nothing

    (4) i == end + 1: Use i as the end and consider merge current Interval with the next one.

    (5) i > end + 1: consider the next Interval.

    Notice if mInts ended, a new Interval should be pushed back with [i, i].

    class SummaryRanges 
        {
        public:
            /** Initialize your data structure here. */
            SummaryRanges() {}
            
            void addNum(int val) 
            {
                mVals.push_back(val);
            }
            
            vector<Interval> getIntervals()
            {
                vector<Interval> ret;
                if(mVals.empty()) return ret;
                sort(mVals.begin(), mVals.end());
                
                int cntInts = 0;    //counter for mInts.
                for(int i = 0; i < mVals.size(); ++i)
                {
                    if(cntInts == mInts.size()) mInts.push_back(Interval(mVals[i], mVals[i]));  //End of mInts, push back new one.
                    //* [ ]: add a new interval in front.
                    else if(mVals[i] < mInts[cntInts].start - 1) mInts.insert(mInts.begin() + cntInts, Interval(mVals[i], mVals[i]));    
                    else if(mVals[i] == mInts[cntInts].start - 1) mInts[cntInts].start = mVals[i];  //[* ]: enlarge the interval in the front
                    else if(mVals[i] <= mInts[cntInts].end) continue;   //[*] : do nothing
                    else if(mVals[i] == mInts[cntInts].end + 1) //[ *]: enlarge the interval in the end
                    {
                        mInts[cntInts].end = mVals[i];
                        if(cntInts != mInts.size() - 1 && mVals[i] >= mInts[cntInts + 1].start - 1)  //Combine with the next one if possible.
                        {
                            mInts[cntInts].end = mInts[cntInts + 1].end;
                            mInts.erase(mInts.begin() + cntInts + 1);
                        }
                    }
                    else    //[ ] *: consider the next interval;
                    { 
                        i--;
                        cntInts++;
                    }
                }
                mVals.clear();  //no need to do again.
                return mInts;
            }
        private:
            vector<int> mVals; 
            vector<Interval> mInts;
        };

  • 0

    sort takes O(m log m), not O(m).


  • 0
    B

    You are right. Thanks for the correction.


Log in to reply
 

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