A lone traveler hikes in the desert She has a single water b

A lone traveler hikes in the desert. She has a single water bottle that allows her to walk k kms before she suffers from dehydration. She has a map of the n water-holes that are scattered along the desert, and can plan her hike in advance, especially the places where she stops to fill her bottle.

Show that if she hikes on a single clear path (i.e., the desert is 1-dimensional) then the greedy algorithm where she stops along the furthest reachable waterhole to fill her bottle is the one that minimizes the number of stop. Describe how to implement the greedy algorithm in O(n log(n)) time.

Solution

In this algorithm the activities are first sorted according to their finishing time, from the earliest to the latest, where a tie can be broken arbitrarily. Then the activities are greedily selected by going down the list and by picking whatever activity that is compatible with the current selection.

What is the running time of this method?

Well, it depends on which sorting algorihtm you use.

The sorting part can be as small as O(n log n) and the other part is O(n), so the total is O(n log n). Theorem :

Greedy-Activity-Selector solves the activity-selection problem.

Proof :

The proof is by induction on n. For the base case, let n = 1. The statement trivially holds.

For the induction step, let n 2, and assume that the claim holds for all values of n less than the current one. We may assume that the activities are already sorted according to their finishing time. Let p be the number of activities in each optimal solution for [1, . . . , n 1] and let q be the number for [1, . . . , n].

                     Here p q holds.

Can you explain why?

It’s because every optimal solution for [1, . . . , n 1] is a solution for [1, . . . , n].                         

How about the fact that p q 1?

How about the fact that p q 1?

Assume that p q 2. Let W be any optimal solution for [1, . . . , n]. Let W0 = W {n} if W contains n and W0 = W otherwise. Then W0 does not contain n and is a solution for [1, . . . , n 1]. This contradicts the assumption that optimal solutions for [1, . . . , n 1] have p activities.