# simple python solution with binary search

• ``````class SummaryRanges(object):
def __init__(self):
self.intervals = []

# 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

``````

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

• 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 = []

# 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
``````

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