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?
Credits:
Special thanks to @yunhong for adding this problem and creating most of the test cases.
这道题说有个数据流每次提供一个数字，然后让我们组成一系列分离的区间，这道题跟之前那道Insert Interval很像，思路也很像，每进来一个新的数字val，我们都生成一个新的区间[val, val]，然后将其插入到当前的区间里，注意分情况讨论，无重叠，相邻，和有重叠分开讨论处理，参见代码如下:
class SummaryRanges { public: /** Initialize your data structure here. */ SummaryRanges() {} void addNum(int val) { Interval cur(val, val); vector<Interval> res; int pos = 0; for (auto a : v) { if (cur.end + 1 < a.start) { res.push_back(a); } else if (cur.start > a.end + 1) { res.push_back(a); ++pos; } else { cur.start = min(cur.start, a.start); cur.end = max(cur.end, a.end); } } res.insert(res.begin() + pos, cur); v = res; } vector<Interval> getIntervals() { return v; } private: vector<Interval> v; };
本文转自博客园Grandyang的博客，原文链接：分离区间的数据流[LeetCode] Data Stream as Disjoint Intervals ，如需转载请自行联系原博主。
