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-triathlon exercise.

Each contestant must jump into a swimming pool and swim 20 laps in the pool, then bike 10 kilometers, then run 5 kilometers. The plan is to send the contestants out in a staggered fashion, via the following rules. The contestants must use the pool one at a time, i.e., first, one contestant swims the 20 laps, gets out, and starts biking. As soon as this first person is out the pool, a second contestant begins swimming the 20 laps; as soon as the contestant is out and starts biking, a third contestant begins swimming, and so on.

Each contestant i has a projected swimming time s_i (the expected time it will take the contestant to complete the 20 laps), a projected biking time b_i (the expected time it will take the contestant to complete the 10 kilometers of biking) and a projected running time r_i (the time it will take the contestant to complete the 5 kilometers running) with 1 ≤ i ≤ n.

Your friend wants to make a schedule for the triathlon: an order in which to sequence the starts of the contestants. Let us 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 triathlon, assuming that they each spend exactly their projected swimming, biking, and running times on the three sports components. Notice that contestants can bike and run simultaneously, but at most one person can be in the pool at any time.

Your tasks in this question are as follows:

1. Devise a greedy algorithm for scheduling these n campers in the best order such that the completion time of the schedule is as small as possible.

2. Show the correctness of your proposed algorithm.

3. Show that the time complexity of your proposed algorithm

Answer rating: 100% (QA)

1 Consider the greedy algorithm is ensure that the completion time of the schedule is as small as possible I propose this algorithm Consider the given ... View the full answer