# O(n) python solution using binary search

• log(N) for searching, but the step before return takes O(N):

``````def insert(self, intervals, newInterval):
[s,e] = newInterval.start, newInterval.end
s_floor = self.binary_search_floor(intervals, s)
e_floor = self.binary_search_floor(intervals, e)
if e_floor>=0: new_e = max(e, intervals[e_floor].end)

if s_floor == -1:
if e_floor==-1:                                #case: adding [1,2] into [[3,4]]
return [[s,e]]+intervals
return [[s,new_e]]+intervals[e_floor+1:]       #case: adding [1,3] into [[2,4]]

elif s>intervals[s_floor].end:                     #case: adding [3,4] into [[1,2]]
return intervals[:s_floor+1]+[[s,new_e]]+intervals[e_floor+1:]

else:
new_s = intervals[s_floor].start               #case: adding [3,5] into [[1,4]]
return intervals[:s_floor]+[[new_s,new_e]]+intervals[e_floor+1:]

def binary_search_floor(self, arr, t):
l,r = 0, len(arr)-1
ans = -1
while (l<=r):
mid = (l+r)/2
if arr[mid].start==t:
return mid
if arr[mid].start<t:
ans = mid
l = mid+1
else:
r = mid-1
return ans``````

• Yours is only O(N) as well, not log(N).

• u r right, slicing 'intervals' makes it O(n).

• It's a real pity, huh? :-D

I also still find it funny how the Python docs for `bisect.insort_left` feel the need to explicitly point out to "Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step"...

• that is the exact mistake I made in this problem -- focusing on the searching part and forgot the last seemingly trivial but time dominating insertion part... Now I know I am not the only one who had this mistake since the Python docs feels the need to point it out :-).

• I am kinda curious about your username @cbmbbz . Does it mean cao bao mai bi biao zi according to your avatar?

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