Binary search + (partial) linear scan, Pythonm beats 94.44% submissions


  • 0
    D
    class Solution(object):
    
        def binary_search(self, intervals, x, left, right):
            if (left > right):
                return None
            mid = right - (right - left)/2
            if ( intervals[mid].start <= x <= intervals[mid].end):
                return mid
            if (x < intervals[mid].start):
                return self.binary_search(intervals, x, left, mid - 1)
            else:
                return self.binary_search(intervals, x, mid + 1, right)
    
        def find_interval_that_contains(self, intervals, x):
            return self.binary_search(intervals, x, 0, len(intervals) - 1)
    
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            if (len(intervals) == 0):
                return [newInterval]
    
            start_index = self.find_interval_that_contains(intervals, newInterval.start)
            end_index = self.find_interval_that_contains(intervals, newInterval.end)
            if (start_index is not None and end_index is None):
    
                leftPart = intervals[0:start_index]
                midPart = [Interval(s=intervals[start_index].start, e=newInterval.end)]
                i = start_index
                while(i < len(intervals) and intervals[i].start < newInterval.end):
                    i = i + 1
                i = len(intervals) - 1 if i > len(intervals) else i
                rightPart = intervals[i:]
                return leftPart + midPart + rightPart
    
            if (start_index is None and end_index is not None):
                i = 0
                while( i < len(intervals) and intervals[i].end < newInterval.start):
                    i = i + 1
                leftPart = intervals[0:i]
                midPart = [Interval(s=newInterval.start, e=intervals[end_index].end)]
                rightPart = [] if end_index == len(intervals)-1 else intervals[end_index+1:]
                return leftPart + midPart + rightPart
    
            if (start_index is None and end_index is None):
                i = 0
                while(i < len(intervals) and intervals[i].start < newInterval.start):
                    i = i + 1
                leftPart = intervals[0:i]
                while(i < len(intervals) and intervals[i].start < newInterval.end):
                    i = i + 1
    
                midPart = [newInterval]
                rightPart = intervals[i:]
                return leftPart + midPart + rightPart
    
            intervals[start_index].end = intervals[end_index].end
            del intervals[start_index+1:end_index+1]
            return intervals
    

Log in to reply
 

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