Introduction to Algorithms, Third Edition

The optimal substructure of the activity-selection problem
We can easily verify that the activity-selection problem exhibits optimal substruc-
ture. Let us denote by
S
ij
the set of activities that start after activity
a
i
finishes and
that finish before activity
a
j
starts. Suppose that we wish to find a maximum set of
mutually compatible activities in
S
ij
, and suppose further that such a maximum set
is
A
ij
, which includes some activity
a
k
. By including
a
k
in an optimal solution, we
are left with two subproblems: finding mutually compatible activities in the set
S
i k
(activities that start after activity
a
i
finishes and that finish before activity
a
k
starts)
and finding mutually compatible activities in the set
S
kj
(activities that start after
activity
a
k
finishes and that finish before activity
a
j
starts). Let
A
i k
D
A
ij
\
S
i k
and
A
kj
D
A
ij
\
S
kj
, so that
A
i k
contains the activities in
A
ij
that finish before
a
k
starts and
A
kj
contains the activities in
A
ij
that start after
a
k
finishes. Thus, we
have
A
ij
D
A
i k
[ f
a
k
g [
A
kj
, and so the maximum-size set
A
ij
of mutually com-
patible activities in
S
ij
consists of
j
A
ij
j D j
A
i k
j C j
A
kj
j C
1
activities.
The usual cut-and-paste argument shows that the optimal solution
A
ij
must also
include optimal solutions to the two subproblems for
S
i k
and
S
kj
. If we could
find a set
A
0
kj
of mutually compatible activities in
S
kj
where
j
A
0
kj
j
>
j
A
kj
j
, then
we could use
A
0
kj
, rather than
A
kj
, in a solution to the subproblem for
S
ij
. We
would have constructed a set of
j
A
i k
j C j
A
0
kj
j C
1 >
j
A
i k
j C j
A
kj
j C
1
D j
A
ij
j
mutually compatible activities, which contradicts the assumption that
A
ij
is an
optimal solution. A symmetric argument applies to the activities in
S
i k
.
This way of characterizing optimal substructure suggests that we might solve
the activity-selection problem by dynamic programming. If we denote the size of
an optimal solution for the set
S
ij
by
cŒi; j 
, then we would have the recurrence
cŒi; j 
D
cŒi; k
C
cŒk; j 
C
1 :
Of course, if we did not know that an optimal solution for the set
S
ij
includes
activity
a
k
, we would have to examine all activities in
S
ij
to find which one to
choose, so that
cŒi; j 
D
(
0
if
S
ij
D ;
;
max
a
k
2
S
ij
f
cŒi; k
C
cŒk; j 
C
1
g
if
S
ij
¤ ;
:
(16.2)
We could then develop a recursive algorithm and memoize it, or we could work
bottom-up and fill in table entries as we go along. But we would be overlooking
another important characteristic of the activity-selection problem that we can use
to great advantage.

---

16.1
An activity-selection problem
417