In general case, vector is OK, it will take O(n) time in each add, and O(1) in get result. But if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size, we'd better use another data structure "set", because the insert operation in vector will cost O(n) time, but it only cost O(log n) in binary search tree, but it will cost O(n) time in getInterval. So use which data structure will depends.

first one is the solution use vector

```
class SummaryRanges {
public:
void addNum(int val) {
auto Cmp = [](Interval a, Interval b) { return a.start < b.start; };
auto it = lower_bound(vec.begin(), vec.end(), Interval(val, val), Cmp);
int start = val, end = val;
if(it != vec.begin() && (it-1)->end+1 >= val) it--;
while(it != vec.end() && val+1 >= it->start && val-1 <= it->end)
{
start = min(start, it->start);
end = max(end, it->end);
it = vec.erase(it);
}
vec.insert(it,Interval(start, end));
}
vector<Interval> getIntervals() {
return vec;
}
private:
vector<Interval> vec;
};
```

and below is another solution use binary search tree.

```
class SummaryRanges {
public:
/** Initialize your data structure here. */
void addNum(int val) {
auto it = st.lower_bound(Interval(val, val));
int start = val, end = val;
if(it != st.begin() && (--it)->end+1 < val) it++;
while(it != st.end() && val+1 >= it->start && val-1 <= it->end)
{
start = min(start, it->start);
end = max(end, it->end);
it = st.erase(it);
}
st.insert(it,Interval(start, end));
}
vector<Interval> getIntervals() {
vector<Interval> result;
for(auto val: st) result.push_back(val);
return result;
}
private:
struct Cmp{
bool operator()(Interval a, Interval b){ return a.start < b.start; }
};
set<Interval, Cmp> st;
};
```