Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Intersect two ordered interval lists: The Crossing Routes.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Two-list interval intersection matches the clues
- 2Keep this true after every move: every discarded interval has been compared with every interval it could overlap
- 3Reach the result within O(m + n)
Rules and pressure
- Target cost: O(m + n)
- State rule: every discarded interval has been compared with every interval it could overlap
Lesson 1 of 3
Live algorithm trace
Two-list interval intersection
Complete execution1 of 6
Compare the first intervals from both sorted lists.
1
i, j = 0, 02
start = max(A[i].start, B[j].start)3
end = min(A[i].end, B[j].end)4
if start <= end: emit intersection5
advance the interval with smaller end6
return intersectionsi = 0j = 0output = []
Truth to preserve / Cost target
Truth to preserve
every discarded interval has been compared with every interval it could overlap
Cost target
O(m + n)
The overlap of two closed intervals starts at the later start and ends at the earlier end. After testing it, advance whichever interval ends first because it cannot overlap any later interval on the other route.
Your call · What should guide every step of this algorithm?