Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 8 / c

Serve customers in nondecreasing service time, with ties broken arbitrarily. The objective in the source includes each customer's own service time, so these are completion times, not only delays before service begins. If the order is $\sigma$, thenTo prove optimality, consider adjacent service times $a>b$ after an elapsed time $P$. Their contributions before an exchange are $(P+a)+(P+a+b)$; after the exchange they are $(P+b)+(P+b+a)$. The total decreases by $a-b>0$. Earlier customers are unaffected, and later customers begin after the same combined duration $a+b$ as before, so their completion times are unchanged.

Repeatedly exchanging adjacent inversions reaches a nondecreasing order without increasing the objective. Hence that order is optimal. Sorting takes $O(n\log n)$ time in a comparison model, followed by a linear traversal to produce the order or compute the total. Equal service times give zero exchange difference and do not affect optimality. If waiting time were instead defined before service, subtracting the order-independent total service time would give the same optimal order.