Data Stream as Disjoint Intervals
要点：因为data stream处理中任何中间结果interval之间都是disjoint的，所以可以直接用binary search tree（而不需要Interval tree）。BST是按interval start存储。
- merge的方式：类似Insert Interval，但是更容易点。先和floor.end比较，然后变换插入Interval的start，然后比较higher.start，变换Interval的end。中间不插入会提前return。
错误点：
- TreeSet => List: toArray() => Array => List: 因为toArray返回Object[]，不能直接cast成Interval[]，所以toArray() args里创建一个正确type的array来fill。 http://stackoverflow.com/questions/174093/toarraynew-myclass0-or-toarraynew-myclassmylist-size
要点：上面的方法是在addNum时候merge，也可以在getIntervals的时候做。也就是说，addNum只是插入(val, val)，可以用一个heap保持按start的顺序插入。然后就类似于merge intervals了，主要是可以merge的情况不pop，而更新heap顶interval.end。唯一差别就是+1也要merge。还有一个注意点，这题是stream，所以要save heap的元素，巧妙的方法是把输出赋值heap，因为输出还是维持start顺序的，和heap是一样的。只是merge了，再利用python heapq是在list上操作的。
错误点：
- heap是不能接受Interval object的，并且tuple是immutable的，所以要用list[list]表示heap中的interval，否则，TypeError: 'tuple' object does not support item assignment
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
from heapq import *
class SummaryRanges(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.intervals = []
self.res = []
def addNum(self, val):
"""
:type val: int
:rtype: void
"""
heappush(self.intervals, [val, val])
def getIntervals(self):
"""
:rtype: List[Interval]
"""
res = []
while self.intervals:
top = heappop(self.intervals)
if res and top[0]<=res[-1][1]+1:
res[-1][1]=max(res[-1][1], top[1]) # error 2: TypeError: 'tuple' object does not support item assignment
else:
res.append([top[0], top[1]])
self.intervals = res
return [Interval(i[0], i[1]) for i in res]
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()