Insert Interval
The problem
Insert a closed interval into a list of closed intervals already sorted by start and mutually non-overlapping. Merge overlaps and return a sorted result. Touching endpoints overlap.
Example
[[1, 2], [5, 8]], new = [2, 6] → [[1, 8]]
Need a hint?
Separate intervals into before, overlapping, and after the new interval.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Copy intervals ending before the new start. While the next start is at most the growing new end, merge by minimizing start and maximizing end. Append the merged interval, then all remaining intervals. Avoid mutating the caller’s interval unless that contract is explicit.
Complexity
O(n) time and O(n) output space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.