343. Songs are stored one after another on a tape, and playing song i requires reading every song before it plus song i. In what order should you store them to minimise expected access time?
MediumGreedy algorithms
Technical
Show model answer
If every song is equally likely, store them in ascending order of length; the expected cost is proportional to the sum of prefix lengths, which a shortest-first order minimises. If song i has access frequency f_i and length L_i, sort by L_i / f_i ascending. Sorting is O(n log n), O(1) extra space with an in-place sort.
Adjacent-swap argument: for two neighbours i then j, only their mutual contribution changes when swapped. Putting i first adds L_i · f_j to j's cost; putting j first adds L_j · f_i to i's cost. So i should come first exactly when L_i · f_j < L_j · f_i, which is the ratio rule. Any order with an inversion can be improved, so the sorted order is optimal.