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