interval_addition.py

# Insert an interval into a list of sorted disjoint intervals. This is a common interview question where the input is a sorted list of disjoint intervals, and your goal is to insert a new interval and merge all necessary intervals returning a final new list.
# For example, if the interval list is [[1,5], [10,15], [20,25]] and you need to insert the interval [12,27]

INPUT = [[1, 5], [10, 15], [20, 25]]
ADDITION = [0,1]
ANSWER = [[1, 5], [10, 27]]


def merge_intervals(interval_1, interval_2):
    lower = min(interval_1[0], interval_2[0])
    upper = max(interval_1[1], interval_2[1])
    return [lower, upper]


def fix_overlap(array, start, end):
    # Merge the intervals that overlap
    overlap_fix = merge_intervals(array[start], array[end])

    # Insert the overlap fix
    array[start] = overlap_fix

    # Remove the overlap "end" element
    del array[end]

    return array


# O(n)
def insert_sorted(intervals, new_interval):
    new_sorted = intervals

    for i, interval in enumerate(intervals):
        if new_interval[0] < interval[0]:
            new_sorted.insert(i, new_interval)
            break

        # elif new_interval[0] == new_interval:
        # Compare max

    return new_sorted


def detect_overlap(intervals):
    for i, _ in enumerate(intervals):
        if i >= len(intervals) - 1:
            break

        if intervals[i][1] >= intervals[i + 1][0]:
            return i

    return None


def insert_interval(intervals, new_interval):
    # Add this array in a sorted manner
    result_array = insert_sorted(intervals, new_interval)

    # Get overlap index from the array to start the while loop
    overlap_index = detect_overlap(result_array)
    if overlap_index is not None:
        print('Overlap detected at', overlap_index)
    else:
        return result_array

    # TODO: - Use start position for overlap check and work always forwards...
    i = 0
    while overlap_index is not None:
        # Fix overlap
        result_array = fix_overlap(result_array, overlap_index,
                                   overlap_index + 1)

        # Update overlap index
        overlap_index = detect_overlap(result_array)
        if overlap_index is not None:
            print('Overlap still detected at', overlap_index)

        # Increment counter
        i = i + 1

    return result_array


# Main execution
def main():
    print(INPUT)
    print(ADDITION, '\n')

    answer = insert_interval(INPUT, ADDITION)
    print('\n', answer, '\n')


# Start program execution
main()