Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Insert one span into ordered territory: The New Bridge.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Insert and merge intervals matches the clues
- 2Keep this true after every move: the output is sorted and nonoverlapping, and the live interval covers every absorbed overlap
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: the output is sorted and nonoverlapping, and the live interval covers every absorbed overlap
Lesson 1 of 3
Live algorithm trace
Insert and merge intervals
Complete execution1 of 6
Copy 1-2 because it ends before the new interval begins.
1
copy intervals ending before new start2
merge every overlapping interval3
append the merged interval4
copy intervals starting after new end5
return outputnewInterval = 4-8output = [1-2]
Truth to preserve / Cost target
Truth to preserve
the output is sorted and nonoverlapping, and the live interval covers every absorbed overlap
Cost target
O(n)
Sorted nonoverlapping intervals split into three regions: spans before the new interval, spans that overlap it, and spans after it. Copy, absorb, then finish.
Your call · What should guide every step of this algorithm?