Simple python solution using heap

  • 0

    addNum O(1)
    getIntervals O(n log(n)) worst-case, but amortizes to O(1) when intervals are highly connected

    Probably not as efficient as a BST in the general case

    import heapq
    class SummaryRanges(object):
        def __init__(self):
            Initialize your data structure here.
            self.heap = []
        def addNum(self, val):
            :type val: int
            :rtype: void
        def getIntervals(self):
            :rtype: List[Interval]
            if len(self.heap) < 1:
                return []
            intervals = [heapq.heappop(self.heap)]
            while len(self.heap) > 0:
                cur = heapq.heappop(self.heap)
                if intervals[-1][1] + 1 >= cur[0]:
                    intervals[-1][1] = max(intervals[-1][1], cur[1])
            self.heap = intervals
            return intervals

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.