## 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;
};
```