simple python solution with binary search


  • 4
    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.


  • 0
    V

    Adapted to use bisect by overloading Interval.__cmp__.

    class SummaryRanges(object):
        Interval.__cmp__ = lambda self, other: cmp(self.start, other.start if isinstance(other, Interval) else other)
    
        def __init__(self):
            self.intervals = []
    
        def addNum(self, val):
            # find location
            pos = bisect.bisect_right(self.intervals, val) - 1
            if 0 <= pos < len(self.intervals) and self.intervals[pos].start <= val <= self.intervals[pos].end:
                return
    
            # insert the interval
            pos += 1
            self.intervals.insert(pos, Interval(val, val))
    
            # merge with next interval
            if pos+1 < len(self.intervals) and self.intervals[pos+1].start == val+1:
                self.intervals[pos].end = self.intervals[pos+1].end
                self.intervals.pop(pos+1)
    
            # merge with prev interval
            if pos-1 >= 0 and self.intervals[pos-1].end == val-1:
                self.intervals[pos-1].end = self.intervals[pos].end
                self.intervals.pop(pos)
    
        def getIntervals(self):
            """
            :rtype: List[Interval]
            """
            return self.intervals
    

Log in to reply
 

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