Medium data structure and algorithm practice puzzle.
Given the CPU time each waiting job needs, return the total time spent waiting if the scheduler always runs the shortest job available. Shortest first is provably optimal for average wait, and the exchange argument is one line: swap any two neighbours where the longer runs first and every job behind them waits less. It is also why it is not what your machine does, since a scheduler that always prefers short jobs starves the long one forever.
Solve it three ways: snap the jigsaw pieces together, fill in the blanks, or type it from scratch against the tests. This one is free.
Browse all 536 puzzles