Suppose you fly a drone from Boulder to Denver to deliver a package. The battery

Question

Suppose you fly a drone from Boulder to Denver to deliver a package. The battery of the drone when fully charged has enough energy to fly k kilometers. Along the flight route from Boulder to Denver there are n wireless charging stations where the drone can stop to charge its battery. Denote by l1 < l2 < · · · < ln the locations of the charging stations along the route with li the distance from Boulder to the ith charging station. The distance between neighboring charging stations is assumed to be at most k kilometers. Your objective is to make as few charging stops as possible along the way. Give an optimal greedy algorithm to determine at which charging stations you would stop and the associated time complexity, and prove that your algorithm does give an optimal solution by showing the greedy choice property and the optimal substructure property

Explanation / Answer

As all the charging station are along the route from boulder to denver we will choose the charging stations towards denver whi will have maximum distance from currenr gas station but less than k.

complexity will be O(n).

It satisfies greedy property as if we are choosing the local optimum that is maximum distance from substation so as to stop as few times in the path as we can. So the total times we stop will come out as mimimum (global optimum).

Optimal substructure :- If we would have chosen any other gas station which would have had less distance from previous gas station, it would have led to the less total distance traveled hence would not be the optimal choice as we need to travel as much distance as possible for greedy approach which would be possible with only one choice that we have chosen.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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