tooling.py

class Solution(object):
    def start_index_search(self, intervals, value, lower, upper):
        """ Return the index that contains the value, or else one right below it"""

        if len(intervals) == 1:
            return 0

        mid = lower + ((upper - lower) // 2)

        current_start = intervals[mid][0]

        if current_start == value:
            return mid

        if (current_start < value) and lower < upper and mid+1 < len(intervals):
            return self.start_index_search(intervals, value, mid+1, upper)
        elif (current_start > value) and lower < upper and mid-1  > -1:
            return self.start_index_search(intervals, value, lower, mid-1)
        
        if current_start > value:
            mid -= 1

        return max(mid, 0)
        
    def is_within_interval(self, intervals, index, value):
        interval = intervals[index]
        return value >= interval[0] and value <= interval[1]
    
    def short_circuit_edges(self, intervals, candidate_interval):

        if candidate_interval[0] > intervals[-1][1]:
            intervals.append(candidate_interval) 
            return (True, intervals)

        if candidate_interval[1] < intervals[0][0]:
            final_intervals = [candidate_interval] + intervals
            return (True, final_intervals)
        
        if candidate_interval[0] <= intervals[0][0] and candidate_interval[1] >= intervals[-1][1]:
            return (True, [candidate_interval])
        
        return False, None


    def clean_up(self, intervals, final_interval):

        start_value = final_interval[0]
        finish_value = final_interval[1]
        
        is_edge, final_intervals = self.short_circuit_edges(intervals, final_interval)
        if is_edge:
            return final_intervals

        begin = self.start_index_search(intervals, start_value, 0, len(intervals))
        end = self.start_index_search(intervals, finish_value, begin, len(intervals))

        final_intervals = intervals[:begin+1]

        #-- If beginning values match, choose our candidate
        if intervals[begin][0] == final_interval[0]:
            final_intervals = intervals[:begin]

        #-- Edge case since we can't "return index below 0" in binary search
        edge_zero_case = False
        if begin == 0: 
            if intervals[0][0] < final_interval[0]:
                final_intervals = [intervals[0]]
            elif intervals[0][0] >= final_interval[0]:
                final_intervals = [final_interval]
                edge_zero_case = True
 
        if not edge_zero_case:
            final_intervals.append(final_interval)

        final_intervals.extend(intervals[end+1:])
        return final_intervals

    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """

        if not intervals:
            return [newInterval]
        
        is_edge, final_intervals = self.short_circuit_edges(intervals, newInterval)
        if is_edge:
            return final_intervals

        new_start = newInterval[0]
        new_end = newInterval[1]

        #-- We can start for the start through binary search, since it's sorted
        #   Almost like first bad version
        start_index = self.start_index_search(intervals, new_start, 0, len(intervals))

        #-- Now find where the end fits within starts
        # end_index_begins = self.start_index_search(intervals, new_end, False, start_index, len(intervals))
        end_index_begins = self.start_index_search(intervals, new_end, start_index, len(intervals))

        #-- Now that we know, we need to figure out if either of these are contained in the intervals identified
        if self.is_within_interval(intervals, start_index, new_start):
            #-- Then we can use the start of the current interval (otherwise, leave as is)
            new_start = intervals[start_index][0]
        
        if self.is_within_interval(intervals, end_index_begins, new_end):
            #-- Then we can use the end as the new interval (otherwise, leave as is)
            new_end = intervals[end_index_begins][1]

        final_interval = [new_start, new_end]

        #-- Get rid of all over intervals
        final_intervals = self.clean_up(intervals, final_interval)

        return final_intervals