Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Minimum Waiting Time

Proving shortest-first

nn people wait in line. Person ii takes tit_i time to be served. Minimize total waiting time (sum of all waiting times).

Example: times = [3, 2, 1]. If order is [3, 2, 1]: person 11 waits 00, person 22 waits 33, person 33 waits 33 + 22 = 55. Total: 00 + 33 + 55 = 88. If order is [1, 2, 3]: person 11 waits 00, person 22 waits 11, person 33 waits 11 + 22 = 33. Total: 00 + 11 + 33 = 44. Better!

What is the optimal order? Can you prove it? The order you choose affects everyone behind.