Insert Interval
intervals is a list of closed [start, end] pairs that are sorted by start and do not overlap. Insert newInterval, merging where it overlaps, and return the list still sorted and non-overlapping. Touching intervals merge ([1, 4] and [4, 5] become [1, 5]). Do it in one pass without re-sorting.
insertInterval([[1, 3], [6, 9]], [2, 5]) -> [[1, 5], [6, 9]] insertInterval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) -> [[1, 2], [3, 10], [12, 16]]
Hints
Hint 1
Insert is three linear phases over the sorted list: copy everything that ends before the new interval starts; absorb everything that starts before the new interval ends by widening it; copy the rest. No sort needed — the invariant gives you O(n).