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
            """
            self.heap.append([val,val])
    
        def getIntervals(self):
            """
            :rtype: List[Interval]
            """
            heapq.heapify(self.heap)
            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])
                else:
                    intervals.append(cur)
            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.