Greedy Algorithm Exchange Proof (Algorithm Design, Chapter 4, 6E)

Working through book, and came across this problem :

6. Your friend is working as a camp counselor, and he is in charge of 
organizing activities for a set of junior-high-school-age campers. One of 
his plans is the following mini-triathalon exercise: each contestant must 
swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The plan is 
to send the contestants out in a staggered fashion, via the following rule: 
the contestants must use the pool one at a time. In other words, first one 
contestant swims the 20 laps, gets out, and starts biking. As soon as this 
first person is out of the pool, a second contestant begins swimming the 
20 laps; as soon as he or she is out and starts biking, a third contestant 
begins swimming . . . and so on.) 

Each contestant has a projected swimming time (the expected time it 
will take him or her to complete the 20 laps), a projected biking time (the 
expected time it will take him or her to complete the 10 miles of bicycling), 
and a projected running time (the time it will take him or her to complete 
the 3 miles of running). Your friend wants to decide on a schedule for the 
triathalon: an order in which to sequence the starts of the contestants. 
Let’s say that the completion time of a schedule is the earliest time at 
which all contestants will be finished with all three legs of the triathalon, 
assuming they each spend exactly their projected swimming, biking, and 
running times on the three parts. (Again, note that participants can bike 
and run simultaneously, but at most one person can be in the pool at 
any time.) What’s the best order for sending people out, if one wants the 
whole competition to be over as early as possible? More precisely, give 
an efficient algorithm that produces a schedule whose completion time 
is as small as possible.

Just fiddling with numbers it becomes pretty obvious the answer is a greedy algorithm to sort in descending order of biking time + running time.

What I am struggling with is my teacher mentioned this as good practice for using the exchange argument/proof, but I can't see how to use it (or anything else) to prove this answer correct.

This problem is answered elsewhere online (I see this variant several places), but as far as I can tell the answer is wrong

note : b_i/r_i stands for bike/ride time of contestant i

We prove this by an exchange argument. Consider any optimal solution, and suppose it does not use this order. Then the optimal solution must contain two contestants i and j so that j is sent out directly after i , but b_i + r_i < b_j + r_j . We will call such a pair (i,j) an inversion . Consider the solution obtained by swapping the orders of i and j . In this swapped schedule, j completes earlier than he/she used to. Also, in the swapped schedule, i gets out of the pool when j previously got out of the pool; but since b_i + r_i < b_j + r_j , i ﬁnishes sooner in the swapped schedule than j ﬁnished in the previous schedule.

My issue with this is bolded, there is no reason to assume that i and j have the same swim time, therefore i will not get out the pool when j got out of the poo;

Am I wrong and this answer is somehow right? If so why? If not what would a correct proof/argument look like?

Solution

I agree with you that this answer overassumes what you mentioned in bold. I was only able to find this text posted at https://www.coursehero.com/file/9692310/HW4S12sol1/ and mirrors thereof. Fortunately, we don't need this assumption to prove the greedy algorithm is optimal with the exchange argument.

To prove it, we will calculate the time each contestant takes in each case and show that the swapping will only reduce the time the last of i or j complete.

We can assume WLOG that the first of i or j starts at time 0.

In the optimal schedule with the inversion (i goes first):

Contestant	Time Finished
i	t_oi = s_i + b_i + r_i
j	t_oj = s_i + s_j + b_j + r_j

Since b_i + r_i < b_j + r_j, it is clear that t_oi < t_oj which means j finishes last in this case.

In the swapped schedule (j goes first):

Contestant	Time Finished
i	t_si = s_i + s_j + b_i + r_i
j	t_sj = s_j + b_j + r_j

We don't know which of the two finishes last, but we can show that t_si < t_oj and t_sj < t_oj which means that either way, the time the last contestant finished has reduced.

Thus, swapping this inversion will only improve the finish time of the last contestant of i or j, and continued swapping of the optimal solution to the greedy solution will not result in a sub-optimal solution. Therefore the greedy solution is optimal.