352. Data Stream as Disjoint Intervals
有序的几个重要数据结构和算法：heap，stack，quicksort，mergesort
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class SummaryRanges(object):
def __init__(self):
self.intervals = []
def addNum(self, val):
heapq.heappush(self.intervals, (val, Interval(val, val)))
def getIntervals(self):
stack = []
print self.intervals
while self.intervals:
idx, cur = heapq.heappop(self.intervals)
if not stack:
stack.append((idx, cur))
else:
_, prev = stack[-1]
if prev.end + 1 >= cur.start:
prev.end = max(prev.end, cur.end)
else:
stack.append((idx, cur))
self.intervals = stack
return list(map(lambda x: x[1], stack))
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()
