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 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 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
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.
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.
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)