Page 221 - Discrete Mathematics and Its Applications
P. 221
200 3 / Algorithms
Proof: We will use a proof by contradiction. Suppose that there is a positive integer n such that
there is a way to make change for n cents using quarters, dimes, nickels, and pennies that uses
fewer coins than the greedy algorithm finds. We first note that q , the number of quarters used
in this optimal way to make change for n cents, must be the same as q, the number of quarters
used by the greedy algorithm. To show this, first note that the greedy algorithm uses the most
quarters possible, so q ≤ q. However, it is also the case that q cannot be less than q. If it were,
we would need to make up at least 25 cents from dimes, nickels, and pennies in this optimal
way to make change. But this is impossible by Lemma 1.
Because there must be the same number of quarters in the two ways to make change, the
value of the dimes, nickels, and pennies in these two ways must be the same, and these coins
are worth no more than 24 cents. There must be the same number of dimes, because the greedy
algorithm used the most dimes possible and by Lemma 1, when change is made using the fewest
coins possible, at most one nickel and at most four pennies are used, so that the most dimes
possible are also used in the optimal way to make change. Similarly, we have the same number
of nickels and, finally, the same number of pennies.
A greedy algorithm makes the best choice at each step according to a specified criterion.
The next example shows that it can be difficult to determine which of many possible criteria to
choose.
EXAMPLE 7 Suppose we have a group of proposed talks with preset start and end times. Devise a greedy
algorithm to schedule as many of these talks as possible in a lecture hall, under the assumptions
that once a talk starts, it continues until it ends, no two talks can proceed at the same time, and
a talk can begin at the same time another one ends. Assume that talk j begins at time s j (where
s stands for start) and ends at time e j (where e stands for end).
Solution: To use a greedy algorithm to schedule the most talks, that is, an optimal schedule, we
need to decide how to choose which talk to add at each step. There are many criteria we could
use to select a talk at each step, where we chose from the talks that do not overlap talks already
selected. For example, we could add talks in order of earliest start time, we could add talks in
order of shortest time, we could add talks in order of earliest finish time, or we could use some
other criterion.
We now consider these possible criteria. Suppose we add the talk that starts earliest among
the talks compatible with those already selected. We can construct a counterexample to see that
the resulting algorithm does not always produce an optimal schedule. For instance, suppose that
we have three talks: Talk 1 starts at 8 a.m. and ends at 12 noon, Talk 2 starts at 9 a.m. and ends
at 10 a.m., and Talk 3 starts at 11 a.m. and ends at 12 noon. We first select the Talk 1 because it
starts earliest. But once we have selected Talk 1 we cannot select either Talk 2 or Talk 3 because
both overlap Talk 1. Hence, this greedy algorithm selects only one talk. This is not optimal
because we could schedule Talk 2 and Talk 3, which do not overlap.
Now suppose we add the talk that is shortest among the talks that do not overlap any of those
already selected. Again we can construct a counterexample to show that this greedy algorithm
does not always produce an optimal schedule. So, suppose that we have three talks: Talk 1 starts
at 8 a.m. and ends at 9:15 a.m., Talk 2 starts at 9 a.m. and ends at 10 a.m., and Talk 3 starts at
9:45 a.m. and ends at 11 a.m. We select Talk 2 because it is shortest, requiring one hour. Once
we select Talk 2, we cannot select either Talk 1 or Talk 3 because neither is compatible with
Talk 2. Hence, this greedy algorithm selects only one talk. However, it is possible to select two
talks, Talk 1 and Talk 3, which are compatible.
However, it can be shown that we schedule the most talks possible if in each step we select
the talk with the earliest ending time among the talks compatible with those already selected.
We will prove this in Chapter 5 using the method of mathematical induction. The first step we
will make is to sort the talks according to increasing finish time. After this sorting, we relabel
the talks so that e 1 ≤ e 2 ≤ ... ≤ e n . The resulting greedy algorithm is given as Algorithm 7. ▲