Answer:
Explanation:
Algorithm:
a. In each day, you will have to loop through the hotels that come to the hotel after you stayed last night.
b. If a hotel 'h' is found at more than 'd' distance away from last stayed hotel, then the hotel previous of 'h' is chosen to wait for that night. This is the greedy step, and you stay in this hotel.
c. The process for steps a and b is then repeated until we've 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'. The best move is to estimate the distance to each hotel twice the whole computation in the scenario.
Thus, the total running time that could occur in the worst case is O(2n) = O(n). This is said to be linear time.
