Data Stream as Disjoint Intervals

Desicription

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

1
2
3
4
5
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class SummaryRanges {
private:
std::function<bool(std::pair<int, int>, std::pair<int, int>)> cmp = [](std::pair<int, int> a, std::pair<int, int> b) {
if(a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> set = std::set<std::pair<int, int>, decltype(cmp)>(cmp);

public:
/** Initialize your data structure here. */
SummaryRanges() = default;

void addNum(int val) {
auto it = set.lower_bound({val, val});
int left = val;
int right = val;
if(it != set.begin() && (--it)->second + 1 < val) {
it++;
}

while(it != set.end() && val + 1 >= it->first && val - 1 <= it->second) {
left = std::min(left, it->first);
right = std::max(right, it->second);
it = set.erase(it);
}
set.insert(it, {left, right});
}

std::vector<std::vector<int>> getIntervals() {
auto res = std::vector<std::vector<int>>();
for(auto num : set) {
res.push_back({num.first, num.second});
}
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();
*/