Problem 2 : Road Trip : Suppose you are going on a road trip with friends. Unfor

Question

Problem 2: Road Trip:

Suppose you are going on a road trip with friends. Unfortunately, your headlights are broken, so you can only drive in the daytime. Therefore, on any given day you can drive no more than d miles. You have a map with n different hotels and the distances from your start point to each hotel x1< x2< ... < xn. Your final destination is the last hotel. Describe an efficient greedy algorithm that determines which hotels you should stay in if you want to minimize the number of days it takes you to get to your destination. What is the running time of your algorithm?

Explanation / Answer

Algorithm:

1. For each day, loop through the hotels which come after the hotel in which you stayed last night.

2. If a hotel 'h' is found which is at more than 'd' distance away from last stayed hotel, then the hotel previous of 'h' is chosen to stay for that night. This is the greedy step and you stay in this hotel.

3. Repeat step 1 and 2 till we have reached the last hotel xn.

Running time:

Notice that the worst case occurs if each hotel is at a distance of successive multiples of 'd'. In such a case, we calculate the distance to each hotel two times in the whole computation.

So, the total running time in worst case is O(2n) = O(n). This is linear time.

--------------

This solution is completely correct. If you have any trouble in understanding it, do let me know in the comments. I'd be glad to help you further.

If helpful, do click on the thumbs up button. Thank you.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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