# Possible O(logN) solution with binary search

• Looking at the problem, the O(N) solution is pretty straightforward, and I thought it's for sure going to TLE. Therefore I come up with an O(logN) solution.

From the problem we know:

• "start" of the intervals are sorted
• intervals are not overlapped (i.e. the end of an interval is smaller than the start of next interval, otherwise they are overlapped and should be merged into one)

from the 2 facts we can draw the following conclusion

• "end" of the intervals are also sorted

(proof: For all i, end_i > start_i > end_(i-1) => end_i > end_(i-1). "end" values are sorted)

When you have sorted integer, you can apply binary search and find the place you need to insert. You will need to do it twice: once for start of interval, once for end of interval

1. start of interval: last_interval_before_insert.end < newInterval.start
2. end of interval: first_interval_after_insert.start > newInterval.end

After you find the start/end of the interval, everything in between should be merged.

The general idea is like that but my code is too ugly so I don't feel like posting them :(

• I think this should be a clear example.

``````def binarySearch(intervals, val):
left, right = 0, len(intervals)-1
while left <= right:
mid = (left + right) / 2
if intervals[mid].start <= val <= intervals[mid].end:
return mid
elif val < intervals[mid].start:
right = mid - 1
else:
left = mid + 1

return left

class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
if len(intervals) == 0:
return [newInterval]

left = binarySearch(intervals, newInterval.start)
right = binarySearch(intervals, newInterval.end)
length = len(intervals)

merge_left = left < length and intervals[left].end >= newInterval.start
merge_right = right < length and intervals[right].start <= newInterval.end
l = left if merge_left or left >= length else left+1
r = right+1 if merge_right else right

start = min(intervals[left].start, newInterval.start) if merge_left else newInterval.start
end = max(intervals[right].end, newInterval.end) if merge_right else newInterval.end

return intervals[:l] + [Interval(start, end)] + intervals[r:]``````

• I got the same idea of finding start and end. But creation of new array still take O(n). So still don't think O(lgN) is possible.

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