Insert Interval
Insert one interval into a sorted non-overlapping interval list and merge overlaps.
Why does this pattern fit?
Restate the exact job
Insert one interval into a sorted non-overlapping interval list and merge overlaps.
Intervals before, overlapping, and after the new interval form three ordered phases.
O(n) time · O(n) output
Using strict overlap tests can mishandle touching endpoints under closed intervals.
How to solve Insert Interval
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Insert one interval into a sorted non-overlapping interval list and merge overlaps.
Why Intervals & sweep line fits
Intervals before, overlapping, and after the new interval form three ordered phases.
State to maintain
A mutable merged interval and output list.
Transition
Append left intervals, absorb all overlaps, append merged interval, then the remainder.
Time and space
O(n) time · O(n) output
Counterexample to the tempting mistake
Using strict overlap tests can mishandle touching endpoints under closed intervals.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.