Your friend is working as a camp counselor and he is in charge of organising act

Question

Your friend is working as a camp counselor and he is in charge of organising activities for a set of junior high school age campers. One of his plans is the following mini-triathalon 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., rst one contestant swims the 20 laps, gets out, and starts biking. As soon as this rst 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 si (the expected time it will take the contestant to complete the 20 laps), a projected biking time bi (the expected time it will take the contestant to complete the 10 kilometers of biking) and a projected running time ri (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 triathalon: 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 nished with all three legs of the triathalon, assuming that they each spend exactly their projected swimming, biking, and running times on the three sport 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.
• 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. (6 points) • Show the correctness of your proposed algorithm. (3 points) • Show that the time complexity of your proposed algorithm. (1 point)

Explanation / Answer

Since any number of participants can bike and run simultaneously hence consider this as a single task and add up the time required to perform these tasks by running a loop from 1 to n(considering indexing is from 1) Note that this will require O(n)

Now consider we have just 2 tasks Task1(Swimming) and Task2(biking and running) represented by arrays "S" and "Task2" respectively In order to complete the marathon in minimum time align the contestants in decreasing order of the time required for Task2 This is because no matter what, 1 contestant can enter the pool only when other is out of it and hence the last contestant to enter the pool will enter it at time = sum of time spend by all other contestants in pool and he will get out at time =  sum of time spend by all contestants in pool and that will remain same irrespective of the order in which contestants enter the pool Hence if ordering is done based on the decreasing order of time required for Task2 then when 1st contestant comes out of pool and performs Task2,his remaining time for Task2 will decrease while 2nd contestant will be in the pool and this cycle will continue for all the other contestants as well thereby,guaranting the minimum time for the marathon

Note that sorting the array in decreasing order based on Task2 requires O(n logn) and the final step to find the time to complete the marathon requires single traversal of array requiring O(n) Hence overall time complexity is O(n) + O(n logn) + O(n) = O(n logn)

I can add the code if you want me to Specify it in comment section

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.