Insert Interval

The Idea

Because the list is already sorted and non-overlapping, only one thing is unknown: where the new block lands.

Copy every interval that ends before the new one starts. Absorb every interval that touches it, widening the block as you go. Copy the rest untouched. No sort, one pass.

Real-World Example

Booking a holiday into a tidy shared calendar. Entries before your trip stay exactly as they are, the days your trip overlaps get swallowed into one "away" block, and everything after it is unaffected.

The Code

booked = [(1, 3), (6, 9), (12, 16)]
new, out, i = [4, 8], [], 0
while i < len(booked) and booked[i][1] < new[0]:
    out.append(booked[i]); i += 1        # ends before the new block starts
while i < len(booked) and booked[i][0] <= new[1]:
    new = [min(new[0], booked[i][0]), max(new[1], booked[i][1])]   # absorb
    i += 1
out.append(tuple(new))
print(out + booked[i:])

booked = [(1, 3), (6, 9)]
new = [2, 5]
i = 0
while i < len(booked) and booked[i][0] ___ new[1]:
  new = [min(new[0], booked[i][0]), max(new[1], booked[i][1])]
  i += 1
print(new)   # [1, 5]