O(n) python solution using binary search


  • 1

    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

  • 1

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


  • 1

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


  • 0

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


  • 0

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


  • 0

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


Log in to reply
 

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