Your friend is working as a camp counselor, and he is in charge of organizing ac

Question

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 lime. 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 schedul~ 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. Please also prove your algorithm.

Explanation / Answer

Hello ,here i wrote my answer please look at once .

Let the contestants be numbered 1 , . . . , n , and let si, bi , ri denote the swimming, biking, and running times of contestant i . Here is an algorithm to produce a schedule: arrange the contestants in order of decreasing bi + ri , and send them out in this order. We claim that this order minimizes the completion time. 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 bi + ri < bj + rj . 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 bi + r i < bj + rj , i finishes sooner in the swapped schedule than j finished in the previous schedule. Hence our swapped schedule does not have a greater completion time, and so t is optimal too. Continuing in this way, we can eliminate all inversions without increasing the completion time. At the end of this process we will have a schedule in the order produced by our our algorithm whose completion is no greater than that of the original optimal order we considered. Thus the order produced by our algorithm must also be optimal.

The time complexity may be the O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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