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, 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?
Problem Analysis:
A simple method is put integers to a set, then iterate data in set to construct the interval list. See code example 1 bellow.
We can construct intervals with vector, when add new integer, insert the integer in proper interval, and merge interval when needed. See code example 2 bellow.
Solution 1:
class SummaryRanges {
public:
/** Initialize your data structure here. */
SummaryRanges() {
}
void addNum(int val) {
data_.insert(val);
}
vector<vector<int>> getIntervals() {
vector<vector<int>> res;
int start = -1;
int end = -1;
for (const auto& item: data_) {
if (start == -1) {
start = item;
end = item;
} else if (item == end + 1) {
end = item;
} else {
res.push_back({start, end});
start = end = item;
}
}
if (start != -1) res.push_back({start, end});
return res;
}
private:
set<int> data_;
};Solution 2:
class SummaryRanges {
public:
/** Initialize your data structure here. */
SummaryRanges() {
}
void addNum(int val) {
vector<int> interval{val, val};
if (data_.empty()) {
data_.push_back(interval);
return;
} int i = 0;
for (; i < data_.size(); ++i)
if (data_[i][0] > val) break; if (i == 0) {
if (val + 1 == data_[i][0]) data_[i][0] = val;
else data_.insert(data_.begin(), interval);
} else {
if (i == data_.size()) {
if (data_[i - 1][1] + 1 == val) data_[i - 1][1] = val;
else if (data_[i - 1][1] < val) data_.push_back(interval);
} else {
if (data_[i - 1][1] < val) {
if (data_[i - 1][1] + 1 == val) {
if (data_[i][0] == val + 1) {
data_[i - 1][1] = data_[i][1];
data_.erase(data_.begin() + i);
} else {
data_[i - 1][1] = val;
}
} else {
if (data_[i][0] == val + 1) data_[i][0] = val;
else data_.insert(data_.begin() + i, interval);
}
}
}
}
}
vector<vector<int>> getIntervals() {
return data_;
}
private:
vector<vector<int>> data_;
};
The two methods’s space complexity are O(n), the first time complexity: addNum is O(lgn), getIntervals is O(n), the second time complexity: addNum is O(n), getIntervals is O(1)