Insert Interval

Core idea: You're handed a list of intervals that is already sorted by start and already non-overlapping — a tidy timeline with gaps between bookings — plus one new interval to slot in. The new interval might land cleanly in a gap, or it might smother several existing intervals at once. The naive move is to dump it on the end, re-sort everything, and merge from scratch in O(n log n). But you're throwing away a gift: the input is already sorted. Exploit that and you never need to sort. Walk the list once in three phases — (1) copy every interval that ends before the new one starts, untouched; (2) absorb every interval that overlaps the new one, growing new.start = min and new.end = max, then emit that single merged interval; (3) copy the rest, untouched. One linear pass, O(n) time, O(n) output.

The problem, rephrased

Imagine your day's calendar is a clean strip of booked time blocks, sorted left-to-right with daylight between them — [[1,3], [6,9]]. A new request arrives: block off [2,5]. That request bleeds into the [1,3] booking and spills into the open gap, so the calendar should become [[1,5], [6,9]]. Your job: given intervals (sorted, non-overlapping) and one newInterval, insert it and merge any overlaps, returning a list that is still sorted and still non-overlapping.

This is LeetCode 57 — Insert Interval.

The function returns a new list — you can leave the input alone.