SKEDSOFT

An iterative greedy algorithm

We easily can convert our recursive procedure to an iterative one. The procedure RECURSIVE-ACTIVITY-SELECTOR is almost "tail recursive" : it ends with a recursive call to itself followed by a union operation. It is usually a straightforward task to transform a tail-recursive procedure to an iterative form; in fact, some compilers for certain programming languages perform this task automatically. As written, RECURSIVE-ACTIVITY-SELECTOR works for any subproblem S_ij, but we have seen that we need to consider only subproblems for which j = n 1, i.e., subproblems that consist of the last activities to finish.

The procedure GREEDY-ACTIVITY-SELECTOR is an iterative version of the procedure RECURSIVE-ACTIVITY-SELECTOR. It also assumes that the input activities are ordered by monotonically increasing finish time. It collects selected activities into a set A and returns this set when it is done.

	GREEDY-ACTIVITY-SELECTOR(s, f)
1 n ← length[s]
2 A ← {a1}
3 i ← 1
4 for m ← 2 to n
5      do if sm ≥ fi
6            then A ← A ∪ {am}
7                 i ← m
8 return A

The procedure works as follows. The variable i indexes the most recent addition to A, corresponding to the activity a_i in the recursive version. Since the activities are considered in order of monotonically increasing finish time, f_i is always the maximum finish time of any activity in A. That is,

Lines 2-3 select activity a₁, initialize A to contain just this activity, and initialize i to index this activity. The for loop of lines 4-7 finds the earliest activity to finish in S_{i.n 1}. The loop considers each activity a_m in turn and adds a_m to A if it is compatible with all previously selected activities; such an activity is the earliest to finish in S_{i.n 1}. To see if activity a_m is compatible with every activity currently in A, it suffices by equation (16.4) to check (line 5) that its start time s_m is not earlier than the finish time f_i of the activity most recently added to A. If activity a_m is compatible, then lines 6-7 add activity a_m to A and set i to m. The set A returned by the call GREEDY-ACTIVITY-SELECTOR(s, f) is precisely the set returned by the call RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n 1).

Like the recursive version, GREEDY-ACTIVITY-SELECTOR schedules a set of n activities in Θ(n) time, assuming that the activities were already sorted initially by their finish times