Greedy

Making the greedy choice
What if we could choose an activity to add to our optimal solution without having
to first solve all the subproblems? That could save us from having to consider all
the choices inherent in recurrence (16.2). In fact, for the activity-selection problem,
we need consider only one choice: the greedy choice.
What do we mean by the greedy choice for the activity-selectionproblem? Intuition suggests that we should choose an activity that leaves the resource available
for as many other activities as possible. Now, of the activities we end up choosing, one of them must be the first one to finish. Our intuition tells us, therefore,
to choose the activity in S with the earliest finish time, since that would leave the
resource available for as many of the activitiesthat follow it as possible. (If more
than one activity in S has the earliest finish time, then we can choose any such
activity.) In other words, since the activities are sorted in monotonically increasing
order by finish time, the greedy choice is activity a1. Choosing the first activity
to finish is not the only way to think of making a greedy choice for this problem;
Exercise 16.1-3 asksyou to explore other possibilities.
If we make the greedy choice, we have only one remaining subproblem to solve:
finding activities that start after a1finishes. Why don’t we have to consider activities that finish before a1starts? We have that s1 < f1, and f1is the earliest
finish time of any activity, and therefore no activity can have a finish time less than
or equal to s1. Thus, allactivities that are compatible with activity a1must start
after a1finishes.
Furthermore, we have already established that the activity-selection problem exhibits optimal substructure. LetSkD fai2 S W si? fkgbe theset ofactivities that
start after activity akfinishes. If we make the greedy choice of activity a1, then S1
remains as the only subproblem to solve.1Optimal substructure tells us that if a1is in the optimal solution, then an optimal solution to the original problem consists
of activity a1and all the activities in an optimal solution to the subproblem S1.
One big question remains: is our intuition correct? Is the greedy choice—in
which we choose the first activity to finish—always part of some optimal solution?
The following theorem shows that it is.
1We sometimes refer to thesets Skas subproblems rather than as just sets of activities. It will
always
be clear from the context whether we are referring to Skas a set of activities or as a subproblem
whose input is that set.
418
Chapter 16
Greedy Algorithms
Theorem 16.1
Consider any nonempty subproblem Sk, and let ambe an activity in Skwith the
earliest finish time. Then amis included in some maximum-size subsetof mutually
compatible activities of Sk.
Proof
Let Akbe a maximum-size subset of mutually compatible activities in Sk,
and let ajbe the activity in Akwith the earliest finish time. If aj D am, we are
done, since we have shown that amis in some maximum-size subset of mutually
compatible activities of Sk. If aj¤ am, let the set A0
kD Ak? fajg [ famg be Ak
but substituting amfor aj. Theactivities in A0
kare disjoint, which follows because
the activities in Akare disjoint, ajis the first activity in Akto finish, and fm? fj.
Since jA0

kj D jAkj, we conclude that A0
kis a maximum-size subset of mutually
compatible activities of Sk, and it includes am.
Thus, we see that although we might be able to solve the activity-selection problem with dynamic programming, we don’t need to.(Besides, we have not yet
examined whether the activity-selection problem even has overlapping subproblems.) Instead, we can repeatedly choose the activity that finishes first, keep only
the activities compatible with this activity, and repeat until no activities remain.
Moreover, because we always choose the activity with the earliest finish time, the
finish times of the activities we...