# Very concise c++ solution.

• 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:
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. */
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;
};``````

• This post is deleted!

• How should we solve the follow up questions about lots of merges?

• This post is deleted!

• This post is deleted!

• A sample run (insert value 7)

First, run `lower_bound` let `it` point to interval `(8,9)` because `8` is the first element that is `>= 7`

``````(0,2) (4,6) (8,9) (12,15)    temp = (7, 7)
^
``````

We decrement `it` because the previous interval can merge 7

``````(0,2) (4,6) (8,9) (12,15)    temp = (7, 7)
^
``````

Now, `it` points to the first mergeable interval (if there is one). In this case, `(4,6)`.
While this interval is mergeable, merge `(4,6)` with `temp` to get

``````(0,2) (8,9) (12,15)          temp = (4, 7)
^
``````

Merge `(8,9)` with `temp` to get

``````(0,2) (12,15)                temp = (4, 9)
^
``````

Can't merge anymore, insert temp

``````(0,2) (4,9) (12,15)          temp = (4, 9)
``````

Done.

• Really elegant!!!

• The most important thing is to define a data structure for interval so that give a number, we can find the interval quickly, and we can add interval to it. std::set can do such operation in O(logN) time.
Then we needs to define the comparator for interval. A single integer can be regarded as a interval [i,i]. When [i,i] is inside [a,b], we like to define a < operator so that [i,i]==[a,b], which is equivalent to:
([i,i] < [a,b]) == false
([a,b] < [i,i]) == false
When this operator is defined, we can easily merge the nearby interval so that the whole series is disjoint.
For follow-up question, we use a cache vector to hold the result. If the added number can be find in existing interval, the output doesn't need any change.

``````class SummaryRanges {
struct Comp {
bool operator () (Interval a, Interval b) {
return a.end<b.start;
}
};
set<Interval, Comp> rbtree_;
vector<Interval> cache_;
bool cache_updated_;
public:
/** Initialize your data structure here. */
SummaryRanges(): cache_updated_(true) {

}

auto iter = rbtree_.find(Interval(val, val));
// If there is an existing range covering val
if (!(iter==rbtree_.end()))
return;
// If val can expand any existing range  or even merge two range
Interval new_interval(val,val);
auto left = rbtree_.find(Interval(val-1, val-1));
auto right = rbtree_.find(Interval(val+1, val+1));
if (!(left==rbtree_.end())) {
new_interval.start = left->start;
rbtree_.erase(left);
}
if (!(right==rbtree_.end())) {
new_interval.end = right->end;
rbtree_.erase(right);
}
rbtree_.insert(new_interval);
cache_updated_ = true;
}

vector<Interval> getIntervals() {
if (cache_updated_) {
cache_updated_ = false;
cache_ = vector<Interval>(rbtree_.begin(), rbtree_.end());
}
return cache_;
}
};

``````

• I found it easier to understand if we simplify

while(it != vec.end() && val+1 >= it->start && val-1 <= it->end)

to

while(it != vec.end() && end+1 >= it->start)

We are basically trying to merge {start, end} with it

• I have a question,,
Since the time complexity of vector.insert is linear..(the memory used by vector is continuous)
I guess the time complexity of this solution should still be O(n)?

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