Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.
The basic idea is to use map : start -> end
where end
is not inclusive.
Invariant is that this map is always disjoint.
class SummaryRanges {
map<int, int> m; // start to end, [x,y)
public:
/** Initialize your data structure here. */
SummaryRanges() {
}
void addNum(int val) {
auto next = m.upper_bound(val); // x .. [,)
if (next != begin(m)) {
auto cur = prev(next);
int end = cur->second;
// adds to end of existing interval
if (val == cur->second) {
int start = cur->first;
end = val+1;
// merge two existing intervals
if (val + 1 == next->first) {
end = next->second;
++next;
m.erase(cur, next);
} else {
m.erase(cur);
}
m.emplace(start, end);
} else if (val > cur->second) { // [) .. x
if (val+1 == next->first) {
int end = next->second;
m.erase(next);
m.emplace(val, end);
} else {
m.emplace(val, val + 1);
}
} else {
// [ x ) --> nothing
}
} else {
int end = val + 1;
// the only situation when it merges is x [x+1, y)
if (end == next->first) {
end = next->second;
m.erase(next);
}
m.emplace(val, end);
}
}
vector<vector<int>> getIntervals() {
vector<vector<int>> res;
res.reserve(m.size());
for (auto[start, end] : m) {
res.emplace_back( vector<int>{start, end-1} );
}
return res;
}
};
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges* obj = new SummaryRanges();
* obj->addNum(val);
* vector<vector<int>> param_2 = obj->getIntervals();
*/