Intervals · LC #57
Insert Interval
Given a sorted non-overlapping interval list and a new interval, insert it at the correct position, merging any intervals that overlap with it.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a sorted non-overlapping list of intervals and a `newInterval`, insert it and merge if necessary. Return the updated list.
Sample I/O
Input: intervals=[[1,3],[6,9]], newInterval=[2,5] Output: [[1,5],[6,9]] Input: intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval=[4,8] Output: [[1,2],[3,10],[12,16]]
Intuition
How to Think About It
Intuition
Because the list is already sorted and non-overlapping, you can identify three disjoint phases in a single left-to-right scan: intervals entirely before the new one, intervals that overlap (which get merged into it), and intervals entirely after.
Core Concept
Three-phase scan: (1) copy all intervals with end < newInterval.start; (2) merge all overlapping intervals by expanding newInterval boundaries; (3) append merged newInterval then copy remaining.
When to use
Inserting a single new event into an already-normalised schedule; maintaining a sorted interval set after each insertion.
When NOT to use
Input list is unsorted - use Merge Intervals instead. Multiple simultaneous insertions - batch and re-merge.
Key Insights
What to Know Cold
- No sorting needed - input is pre-sorted; single O(n) pass suffices.
- Phase boundary conditions: end < newStart (before) vs start > newEnd (after) vs overlap.
- Expand newInterval in-place: newStart = min(newStart, cur.start), newEnd = max(newEnd, cur.end).
- The merged interval is appended exactly once after phase 2.
- Works correctly when newInterval doesn't overlap anything - phases 2 is simply skipped.
1 example
Worked Examples
Insert booking into calendar
Calendar has [[1,2],[3,5],[6,7],[8,10],[12,16]]; insert [4,8].
Three-phase single pass - no sort needed.
Output: [[1,2],[3,10],[12,16]]
Real-time scheduling systems insert events and immediately need the normalised non-overlapping set.