Problem context and objectives
Mission briefing
Matchmaking coordinator · Urgent players and jobs compete for limited slots
Keep the best next candidate available without sorting everything again: The Rope Foundry.
A stale priority frontier increases wait time for everyone.
How you win
- 1Recognize when Optimal merge min-heap matches the clues
- 2Keep this true after every move: the heap contains exactly the current unmerged rope lengths
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: the heap contains exactly the current unmerged rope lengths
Lesson 1 of 3
Live algorithm trace
Optimal merge min-heap
Complete execution1 of 6
2
root
3
4
6
Heapify four rope lengths so the shortest is always exposed.
1
heapify all rope lengths2
while more than one rope remains3
pop two shortest4
join them and add to total cost5
push the joined rope6
return totalheap = [2,3,4,6]total = 0
Truth to preserve / Cost target
Truth to preserve
the heap contains exactly the current unmerged rope lengths
Cost target
O(n log n)
Every joined length may be paid again in later joins. Combining the two shortest ropes first keeps repeatedly charged intermediate lengths as small as possible.
Your call · What should guide every step of this algorithm?