Insert Interval

1. The obvious way

   Append and run the whole merge-intervals routine: O(n log n).

2. The key insight

   Walk through once. Phase 1: while an interval ends before the new start, copy it. Phase 2: while an interval starts at or before the new end, grow the new interval to cover it (min of starts, max of ends); then add the grown interval. Phase 3: copy the rest. O(n) with no sorting.

3. The algorithm
   1. Copy intervals whose end is smaller than the new start.
   2. While an interval's start <= new end, merge it into the new interval.
   3. Add the merged new interval.
   4. Copy all remaining intervals.

Watch it run

result: 1-2

def insert(intervals, new_interval):
    result = []
    position = 0
    count = len(intervals)
    while position < count and intervals[position][1] < new_interval[0]:
        result.append(intervals[position])                 # clearly before the new one
        position += 1
    while position < count and intervals[position][0] <= new_interval[1]:
        new_interval = [min(new_interval[0], intervals[position][0]),
                        max(new_interval[1], intervals[position][1])]   # swallow what touches it
        position += 1
    result.append(new_interval)
    result.extend(intervals[position:])                    # clearly after the new one
    return result

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.