Intermediate · Module 15 · Lesson 4
Insert interval
Preserve sorted non-overlapping ranges.
15–25 min readLesson 86 of 123
Lesson 86 of 123
1d streakTheory lesson · Step-by-step
Understand Insert interval
Preserve sorted non-overlapping ranges.
Worked approach
Trace the reasoning step by step
- 1Copy intervals ending before the new interval.
- 2Merge every overlapping interval.
- 3Emit the merged interval.
- 4Copy remaining intervals.
Concrete example
Insert [4,8] into [[1,2],[3,5],[9,10]].
- 1Keep [1,2].
- 2Merge [3,5] with [4,8] to [3,8].
- 3Keep [9,10].
Result is [[1,2],[3,8],[9,10]].
What must remain true (Loop Invariant)
Intervals emitted before the active merge cannot overlap the inserted range.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Sort and scan
O(n log n)
O(n)
Sorting establishes the order that makes one linear scan possible.When to use it
- Autocomplete, dictionary prefixes, wildcard matching, overlap, and scheduling.
- Sharing common string prefixes.
- Reducing range problems to ordered start/end events.
Common mistakes
- Forgetting terminal markers in a trie.
- Treating touching intervals as overlap without checking the problem convention.
- Processing equal-time events in the wrong order.
Practice prompts
- Reproduce the worked Insert interval example without looking at the trace.
- Change one input condition and explain whether the Insert interval invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.