Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Pair the heaviest person with the lightest possible partner: The Rescue Pairs.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Two-ended greedy pairing matches the clues
- 2Keep this true after every move: every unassigned person lies between light and heavy, and each counted boat is unavoidable
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: every unassigned person lies between light and heavy, and each counted boat is unavoidable
Lesson 1 of 3
Live algorithm trace
Two-ended greedy pairing
Complete execution1 of 5
Sort weights and place pointers at the lightest and heaviest people.
1
sort weights2
light = 0; heavy = n - 13
count one boat for heavy4
if light + heavy <= limit: light += 15
heavy -= 16
return boatslimit = 4boats = 0
Truth to preserve / Cost target
Truth to preserve
every unassigned person lies between light and heavy, and each counted boat is unavoidable
Cost target
O(n log n)
The heaviest remaining person must take a boat. If they can pair with the lightest, that pairing cannot hurt any future solution; otherwise they cannot pair with anyone and must go alone.
Your call · What should guide every step of this algorithm?