simple python solution with binary search


  • 3
    B
    class SummaryRanges(object):
        def __init__(self):
            self.intervals = []
    
        def addNum(self, val):
            # find location
            low, high = 0, len(self.intervals) - 1
            while low <= high:
                mid = (low + high) // 2
                elem = self.intervals[mid]
                if elem.start <= val <= elem.end:
                    return
                elif elem.start > val:
                    high = mid - 1
                else:
                    low = mid + 1
    
            # insert the interval
            pos = min(low, high) + 1
            self.intervals[pos:pos] = [Interval(val, val)]
    
            # merge with next interval
            if pos + 1 < len(self.intervals) and val == self.intervals[pos + 1].start - 1:
                self.intervals[pos].end = self.intervals[pos + 1].end
                self.intervals[pos + 1:pos + 2] = []
    
            # merge with prev interval
            if pos - 1 >= 0 and val == self.intervals[pos - 1].end + 1:
                self.intervals[pos - 1].end = self.intervals[pos].end
                self.intervals[pos:pos + 1] = []
    
        def getIntervals(self):
            return self.intervals
    
    

  • 0
    X

    How about the time complexity? I think it's still O(n), since you have to use slice to remove elements from intervals after binary search.


Log in to reply
 

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