An activity-selection problem

An activity-selection problem

Let set S = {a₁, a₂, . . . ,a_n}is of ‘n’ proposed activities that wish to use a resource, which can serve only one activity at a time. 

Each activity a_i has a start time s_i and a finish time f_i, where 0 ≤ s_i < f_i < ∞. Assume that the activities are sorted in monotonically increasing order of finish time: f₁ ≤  f₂ ≤ . . . ≤ f_n-1 ≤  f_n.

In activity-selection problem, aim is to select a maximum-size subset of mutually compatible activities. Activities a_i and a_j are compatible if the intervals [s_i, f_i ) and [s_j, f_j ) do not overlap.

The optimal substructure of the activity-selection problem

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. 

To find a maximum set of mutually compatible activities in S_ij , suppose that A_ij is a maximum set , which includes some activity a_k. 

By including a_k in an optimal solution, there are two sub problems: 

i) finding mutually compatible activities in the set S_ik (activities that start after activity ai finishes and that finish before activity ak starts) and, 

ii) finding mutually compatible activities in the set S_kj (activities that start after activity ak finishes and that finish before activity aj starts).

Let A_ik = A_ij ∩ S_ik and A_kj = A_ij ∩ S_kj , so that A_ik 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 = A_ik U {a_k} U A_kj , and so the maximum-size set A_ij of mutually compatible

activities in S_ij consists of |A_ij | = |A_ik| + |A_kj | + 1 activities.

If we denote the size of an optimal solution for the set S_ij by c[i, j ], then we would have the recurrence 

If an optimal solution for the set S_ij includes activity a_k 

is not known then all activities in S_ij has to be examined to find which one to choose, so that

A recursive algorithm can be developed and memoize it, or work bottom-up and fill in table entries. 

But another important characteristic of the activity-selection problem that is overlooked is to use the greedy choice.

Making the greedy choice

The greedy choice for the activity-selection is to choose an activity that leaves the resource available for as many other activities as possible.

The choice is to choose the activity in S with the earliest finish time, since that would leave the resource available for as many of the activities that follow it as possible. Since the activities are sorted in monotonically increasing order by finish time, the greedy choice is activity a₁. If greedy choice is made, only one remaining sub problem to solve is finding activities that start after a₁ finishes. There is no need to consider activities that finish before a1 starts.

The algorithm works like :

1) Select the first activity from the sorted array and put in a set A.
2) Do following for remaining activities in the sorted array.

       a) If the start time of second activity is greater than or equal to the finish time of                           previously selected activity then select this activity and put it in a set A.

The procedure GREEDY-ACTIVITY-SELECTOR 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 schedules a set of n activities in θ (n) time.

Example:

In above figure highlighted activities a1,a3,a6,a8 form the maximum subset of mutually compatible activities since there start finish times are greater than start times of already selected activities.