Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Give each child the smallest sufficient gift: The Cookie Pact.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Sorted greedy matching matches the clues
- 2Keep this true after every move: matched children use the smallest cookies capable of satisfying them
- 3Reach the result within O(n log n + m log m)
Rules and pressure
- Target cost: O(n log n + m log m)
- State rule: matched children use the smallest cookies capable of satisfying them
Lesson 1 of 3
Live algorithm trace
Sorted greedy matching
Complete execution1 of 4
Sort both sides and compare their smallest remaining values.
1
sort greed and cookie sizes2
child = cookie = 03
if cookie is large enough: match child4
always advance cookie5
return matched childrengreed = [1,2,3]cookies = [1,1]matched = 0
Truth to preserve / Cost target
Truth to preserve
matched children use the smallest cookies capable of satisfying them
Cost target
O(n log n + m log m)
Process children by increasing greed and cookies by increasing size. A too-small cookie can satisfy nobody later; the first sufficient cookie should serve the least-demanding remaining child.
Your call · What should guide every step of this algorithm?