Implement a data structure with the following methods:
StreamSummary() constructs a new instance.
add(int val) adds the number val to the instance.
int[][] get() returns a sorted list of disjoint intervals summarizing the numbers we've seen so far.
Constraints
n ≤ 10,000 where n is the number of calls to add
m ≤ 10,000 where n is the number of calls to get
Example 1
Input
methods = ["constructor", "add", "add", "add", "add", "get"]
arguments = [[], [1], [3], [2], [9], []]`
Output
[None, None, None, None, None, [
[1, 3],
[9, 9]
]]
Explanation
s = StreamSummary()
s.add(1)
s.add(3)
s.add(2)
s.add(9)
s.get() == [[1, 3], [9, 9]]
Example 2
Input
methods = ["constructor", "add", "add", "add", "add", "get"]
arguments = [[], [1], [2], [4], [3], []]`
Output
[None, None, None, None, None, [
[1, 4]
]]
Explanation
s = StreamSummary()
s.add(1)
s.add(2)
s.add(4)
s.add(3)
s.get() == [[1, 4]]
由于 SortedDict 内部使用的是平衡树，因此 add 时间复杂度为 $O(logn)$， get 时间复杂度为 $O(m)$，m 为合并后的区间个数。
这两种方法都可以，大家可以根据 add 和 get 的调用频率以及 m 和 n 的大小关系决定使用哪一种。
代码
代码支持：Python3
Python3 Code:
from sortedcontainers import SortedDict
class StreamSummary:
def __init__(self):
self.start = SortedDict()
self.end = SortedDict()
def add(self, val):
if val - 1 in self.end and val + 1 in self.start:
# [a, val-1] + [val,val] + [val+1, b] -> [a, b]
self.end[self.start[val + 1]] = self.end[val - 1]
self.start[self.end[val - 1]] = self.start[val + 1]
del self.start[val + 1]
del self.end[val - 1]
elif val - 1 in self.end:
# [a, val -1] + [val, val] -> [a, val]
self.end[val] = self.end[val - 1]
self.start[self.end[val]] = val
del self.end[val - 1]
elif val + 1 in self.start:
# [val,val] + [val+1, b] -> [val, b]
self.start[val] = self.start[val + 1]
self.end[self.start[val]] = val
del self.start[val + 1]
else:
self.start[val] = val
self.end[val] = val
def get(self):
# iterate start or end get same correct answer
ans = []
for s, e in self.start.items():
ans.append([s, e])
return ans
