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

Each contestant has a projectedswimming time(the expected time it will take himor her to complete the 20 laps), a projectedbiking time(the expected time it will takehim or her to complete the 10 miles of bicycling), and a projectedrunning time(thetime it will take him or her to complete the 3 miles of running). Your friend wants todecide on aschedulefor the triathlon: an order in which to sequence the starts of thecontestants. Let’s say that thecompletion timeof a schedule is the earliest time at whichall contestants will be finished with all three legs of the triathlon, assuming they eachspend 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 personcan be in the pool at any time.) Whats the best order for sending people out, if one wantsthe whole competition to be over as early as possible? More precisely, give an efficientalgorithm that produces a schedule whose completion time is as small as possible.

Check the explanation

Explanation:

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 statement after reading the question:

Each friend or person take own expected time to complete the swimming, running, and biking. It means that is most probably different time for every person to complete the task.

TT : It is total time to completed all the task by all friends.

TST: It is total swim time to finish the swimming by individual person.

TBT: It is total bike time to finish the riding by individual person.

TRT: It is total run time to finish the running by individual person.

Therefore, according to the given data it is clear that we can’t optimum the swimming time because swim task not allow concurrently swim or we can say parallel swim.

So, total swim time take as it is.

Therefore, there is only way to optimize the time to use bike time or running time because in both task two student can perform both task bike/run parallelly.

Consider the worst-case condition:

When student going in the queue then the first student has maximum swim time, minimum bike and running time but the last student has minimum swim time and maximum bike/run time.

So, optimize the total time we can reverse the queue means you can go for n-1 to 1.

The student goes in that order which take maximum running and riding time compare to swimming time.

So, you can sort the student in that order minimum swim time and maximum running and bike riding time.

Kindly check the attached image.

2.

Step 1: Calculate the sum of TBT & TRT for each camper, Total_BR = TBT(Bi)+ TRT(Ri).

Step 2: Sort all the campers in the order minimum swim time and maximum bike riding or running time.

Step 3: Send the campers in the order above to ensure minimum or optimum completion time. as like shown in figure.

Swim time of all Total Bike or Running time for all Total Time to be optimized

3.  

Time complexity of the proposed algorithm:

O(n) takes time to sort the student friend list from maximum to minimum time based on the running time.

O(n) takes time to sort the student friend list from maximum to minimum which is already sort based on bike time.

O(n) takes time to sort the student friend list from minimum to maximum which is already sort based on swimming time.

Therefore, the total running time is 3*O(n).

Hence, the proposed algorithm total running time complexity is = O(n)+O(n)+O(n) = O(n)

Please note that: sorting takes O(n) time, because input activities already sorted due to bike or swimming time. By chance input elements are not sorted then it takes O(n log n) time.