Appreciate it. You are trying to schedule triathlon contestants so that the tria

Question

Appreciate it.

You are trying to schedule triathlon contestants so that the triathlon completes as early in the day as possible. (The triathlon completes when all the contestants are done.) Each contestant has a projected swimming time, running time, and biking time. Since the pool is very small only one contestant can be in the pool at a time. Any number of contestants can be biking and running at the same time. The contestants first swim, then bike and finally run. Assuming that each contestant will complete each event in their projected time, what is the best order to send the people out, you want the whole competition to over as soon as possible? That is, give and efficient algorithm that produces a schedule whose completion time is as early as possible. Sort the contestants in decreasing or increasing (Circle correct ordering) order of ___ Using an efficient comparison sort the above step will have a time efficiency of Prove that your algorithm is correct using an exchange argument. You must use the following notation: S_1: i^th contestants bike time B_1: i^th contestants run time; R_1: i^th contestants swim time; If your argument involves different orderings make sure your notation clearly differentiates the two orderings. Follow the structure of the proof in class used to prove correctness of the algorithm that solves Minimizing the Total Weighted Time to Completion. There will be slight differences since the function to be minimized here does not involve weights.

Explanation / Answer

Let contestants be numbered 1 , 2 ,...,n and let s i ,b i ,r i 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 b i + r i and send them out in this order. We claim that this order minimizes the completion time. We prove this in the following way. 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 b i + r i

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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