Transform data into multiple disjoint intervals

  Give you a nonnegative integer  a1, a2, ..., an  Composed of data stream input , Please summarize the numbers you have seen so far into a list of disjoint intervals .

Realization  SummaryRanges  class ：

• SummaryRanges()  Initialize the object with an empty data stream .
• void addNum(int val)  Add an integer to the data stream  val .
• int[][] getIntervals()  Disjoint interval  [starti, endi]  Returns a summary of integers in the data stream in the form of a list .

Example ：

 Input ：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
 Output ：
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

explain ： SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // return [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // return [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // return [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

Tips ：

• 0 <= val <= 10^4
• Call at most  addNum  and  getIntervals  Method  3 * 10^4  Time

class SummaryRanges:
def __init__(self):
self.rec = set()
self.s = list()
def binarySearch_l(self, x: int):
s = self.s
l, r = 0, len(s) - 1
while l < r:
mid = l + r >> 1
if s[mid][0] >= x:
r = mid
else:
l = mid + 1
return l
def binarySearch(self, x: int):
s = self.s
l, r = 0, len(s) - 1
while l < r:
mid = l + r >> 1
if s[mid][1] >= x:
r = mid
else:
l = mid + 1
return l
def addNum(self, val: int) -> None:
rec, s = self.rec, self.s
if val in rec:
return
else:
if val - 1 not in rec and val + 1 not in rec:
s.append([val, val])
s.sort()
elif val - 1 in rec and val + 1 not in rec:
p = self.binarySearch(val - 1)
s[p][1] = val
elif val - 1 not in rec and val + 1 in rec:
p = self.binarySearch_l(val + 1)
s[p][0] = val
else:
p = self.binarySearch(val)
s[p - 1][1] = s[p][1]
s.pop(p)
rec.add(val)
def getIntervals(self) -> List[List[int]]:
return self.s