Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Minimize the sum of completion times: The Shortest Work First.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Shortest-processing-time scheduling matches the clues
- 2Keep this true after every move: the scheduled prefix is nondecreasing and has minimum completion sum among its jobs
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: the scheduled prefix is nondecreasing and has minimum completion sum among its jobs
Lesson 1 of 3
Live algorithm trace
Shortest-processing-time scheduling
Complete execution1 of 6
Sort by duration; swapping any long-before-short inversion cannot improve the old order.
1
sort durations ascending2
elapsed = total = 03
for each duration4
elapsed += duration5
total += elapsed6
return totaloriginal = [3,1,2]sorted = [1,2,3]
Truth to preserve / Cost target
Truth to preserve
the scheduled prefix is nondecreasing and has minimum completion sum among its jobs
Cost target
O(n log n)
Run jobs from shortest duration to longest. Swapping an inverted adjacent pair never increases later completion times and reduces the earlier completion by the duration difference.
Your call · What should guide every step of this algorithm?