Hints — p47 Insert Interval

Hint 1. The lazy approach: append new to the list, sort, run Merge Intervals. O(n log n). It works — but you’re wasting the fact that the input is ALREADY sorted and disjoint.

Hint 2. Partition existing intervals into three groups relative to new:

  1. Before: end < new.start — copy as-is.
  2. Overlap: start ≤ new.end AND end ≥ new.start — must merge with new.
  3. After: start > new.end — copy as-is.

Because input is sorted, these groups appear in order. Walk through them in 3 phases.

Hint 3. While processing the overlap group, EXPAND new:

new = [min(new[0], i[0]), max(new[1], i[1])]

Both min and max are needed.

Hint 4. After the overlap loop, REMEMBER to append the now-expanded new exactly once, then continue with the “after” intervals.

Hint 5. Senior-level optimization: instead of scanning to find the phase boundaries, BINARY-SEARCH for them.

  • Left boundary: bisect_left(ends, new.start).
  • Right boundary: bisect_right(starts, new.end).
  • Merge the slice in between; rebuild.

O(log n + k) where k = #intervals merged.

If still stuck: see solution.py.