Greedy Algorithms and Exchange Arguments

Scenario: You play on a local game show where you will complete n different challenges and try to make as much money as possible. The ith challenge takes t_i minutes to complete. You start off with winnings of $1000 but will lose one dollar per minute for each challenge that is not yet completed. In other words, if you complete challenge i at time f(i), you lose f(i) dollars in total for that challenge. Your goal is to order the challenges to lose as little as possible. Assume the times t_i are short enough so no matter what order you choose, your winnings will always be positive.

a) Suppose t₁ = 2, t₂ = 5, t₃ = 1

What is the optimal ordering? (to minimize money lost)

How much do you lose from your initial $1000 in winnings?

b) One of the orderings below is guaranteed to be optimal. Select the correct one.

Sort Challenges by:

-Randomly

-Increasing t_i

-Decreasing t_i

c) Prove that the ordering you selected always finds an optimal solution. Use an exchange argument.