Activity Selection Problem : “Schedule maximum number of compatible activities that need exclusive access to resources likes processor, class room, event venue etc.”

  • Span of activity is defined by its start time and finishing time. Suppose we have such n activities.
  • Aim of algorithm is to find optimal schedule with maximum number of activities to be carried out with limited resources. Suppose S = {a1, a2, a3, .. an} is the set of activities that we want to schedule.
  • Scheduled activities must be compatible with each other. Start time of activities is let’s say si and finishing time is fi, then activities i and j are called compatible if and only if fi < sj or fj < si. In other words, two activities are compatible if their time durations do not overlap.
  • Consider the below time line. Activities {A1, A3} and {A2, A3} are compatible set of activities.
  • For given n activities, there may exist multiple such schedules. Aim of activity selection algorithm is to find out the longest schedule without overlap.
  • Greedy approach sort activities by their finishing time in increasing order, so that f1 ≤ f2 ≤ f3 ≤ . . . ≤ fn. By default it schedules the first activity in sorted list. Subsequent next activities are scheduled whose start time is larger than finish time of previous activity. Run through all possible activities and do the same.
Activity Selection Problem
  • Consider the activity set A = {A1, A2, A3, A4, A5, A6, A7, A8, A9}, their start time S = {1, 4, 5, 2, 6, 3, 10, 12, 11} and finish time F = {4, 5, 7, 9, 10, 14, 15, 16, 17}. If we first select activity A4 for scheduling, we will end up with two activities {A4, A7}.
  • If we select A1 followed by A6, we end up with {A1, A6} only.
  • Whereas, greedy algorithm schedules {A1, A2, A3, A7}, which is the largest possible set.

Algorithm for Activity Selection Problem

Algorithm ACTIVITY_SELECTION(A, S)
// A is Set of n activities sorted by finishing time.
// S = { A[1] }, solution set, initially which contains first activity

j ← 2
while j  ≤  n do
  if fi  ≤  sj then
    S ← S union A[ j ]
    i ← j
  end
  j ← j + 1
  i ← i – 1
end

Complexity Analysis

  • Brute force approach leads to (n – 1) comparison for each activity to find next compatible activity. So it will run in O(n2) time.
  • Sorting of activities by their finishing time takes O(n.log2n) time. After sorting activities, one scan is required to select activities, which will take O(n) time. So total time required for greedy activity selection is O(n + nlog2n) = O(nlog2n)

Example

Example: Given following data, determine the optimal schedule using greedy approach. A = <A1, A2, A3, A4, A5, A6>, S = <1, 2, 3, 4, 5, 6>, F = <3, 6, 4, 5, 7, 9>

Solution:

First of all, sort all activities by their finishing time.

ActivityA1A3A4A2A5A6
fi345679
si134256

Following chart shows the time line of all activities

Activity Selection Problem using greedy algorithm

Let us now check the feasible set of activities.

A1 is already selected, so S = < A1>

f1 > s2, so A1 and A2 are not compatible. Do check for next activity

f1 ≤ s3, so A1 and A3 are compatible. Schedule A3, S = <A1, A3>

f3 ≤ s4, so A3 and A4 are compatible. Schedule A4, S = <A1, A3, A4>

f4 ≤ s5, so A4 and A5 are compatible. Schedule A5, S = <A1, A3, A4, A5>

 f5 > s6, so A5 and A6 are not compatible.  And there is no more activity left to check. Hence final schedule is, S = <A1, A3, A4, A5>

Example: Given following data, determine the optimal schedule for activity selection using greedy algorithm. A = <A1, A2, A3, A4, A5, A6, A7, A8>, S = <1, 2, 3, 4, 5, 6, 7, 8>, F = <4, 3, 7, 5, 6, 8, 10, 9>

Solution:

First of all sort all activities by their finishing time.

ActivityA2A1A4A5A3A6A8A7
fi345678910
si21453687
Activity Selection Problem example

A2 is already selected, so S = < A2>

f2 > s1, so A1 and A2 are not compatible. Do check for next activity

f2 ≤ s4, so A2 and A4 are compatible. Schedule A3, S = <A2, A4>

f4 ≤ s5, so A4 and A5 are compatible. Schedule A5, S = <A2, A4, A5>

f5 > s3, so A3 and A5 are not compatible. Do check for next activity

f5 ≤ s6, so A5 and A6 are compatible. Schedule A6, S = <A2, A4, A5, A6>

f6 ≤ s8, so A6 and A6 are compatible. Schedule A8, S = <A2, A4, A5, A6, A8>

f8 > s7, so A8 and A7 are not compatible. And there is no more activity left to check.

So final schedule is, S = <A2, A4, A5, A6, A8>


Additional Reading: Wiki