Activity Selection Problem – Scheduling Optimal Number of Activities

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 = {a₁, a₂, a₃, .. a_n} 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 s_i and finishing time is f_i, then activities i and j are called compatible if and only if f_i < s_j or f_j < s_i. In other words, two activities are compatible if their time durations do not overlap.
• Consider the below time line. Activities {A₁, A₃} and {A₂, A₃} 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 f₁ ≤ f₂ ≤ f₃ ≤ . . . ≤ f_n. 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.

• Consider the activity set A = {A₁, A₂, A₃, A₄, A_5, A₆, A₇, A₈, A₉}, 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 A₄ for scheduling, we will end up with two activities {A₄, A₇}.
• If we select A₁ followed by A₆, we end up with {A₁, A₆} only.
• Whereas, greedy algorithm schedules {A₁, A₂, A₃, A₇}, 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  ≤  si 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(n²) time.
• Sorting of activities by their finishing time takes O(n.log₂n) 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 + nlog₂n) = O(nlog₂n)

Example

Example: Given following data, determine the optimal schedule using greedy approach. A = <A₁, A₂, A₃, A₄, A₅, A₆>, 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.

Activity	A1	A3	A4	A2	A5	A6
fi	3	4	5	6	7	9
si	1	3	4	2	5	6

Following chart shows the time line of all activities

Let us now check the feasible set of activities.

A₁ is already selected, so S = < A₁>

f₁ > s₂, so A₁ and A₂ are not compatible. Do check for next activity

f₁ ≤ s₃, so A₁ and A₃ are compatible. Schedule A₃, S = <A₁, A₃>

f₃ ≤ s₄, so A₃ and A₄ are compatible. Schedule A₄, S = <A₁, A₃, A₄>

f₄ ≤ s₅, so A₄ and A₅ are compatible. Schedule A₅, S = <A₁, A₃, A₄, A₅>

 f₅ > s₆, so A₅ and A₆ are not compatible.  And there is no more activity left to check. Hence final schedule is, S = <A₁, A₃, A₄, A₅>

Example: Given following data, determine the optimal schedule for activity selection using greedy algorithm. A = <A₁, A₂, A₃, A₄, A₅, A₆, A₇, A₈>, 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.

Activity	A2	A1	A4	A5	A3	A6	A8	A7
fi	3	4	5	6	7	8	9	10
si	2	1	4	5	3	6	8	7

A₂ is already selected, so S = < A₂>

f₂ > s₁, so A₁ and A₂ are not compatible. Do check for next activity

f₂ ≤ s₄, so A₂ and A₄ are compatible. Schedule A₃, S = <A₂, A₄>

f₄ ≤ s₅, so A₄ and A₅ are compatible. Schedule A₅, S = <A₂, A₄, A₅>

f₅ > s₃, so A₃ and A₅ are not compatible. Do check for next activity

f₅ ≤ s₆, so A₅ and A₆ are compatible. Schedule A₆, S = <A₂, A₄, A₅, A₆>

f₆ ≤ s₈, so A₆ and A₆ are compatible. Schedule A₈, S = <A₂, A₄, A₅, A₆, A₈>

f₈ > s₇, so A₈ and A₇ are not compatible. And there is no more activity left to check.

So final schedule is, S = <A₂, A₄, A₅, A₆, A₈>

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

• Binary Knapsack Problem
• Fractional Knapsack Problem
• Job Scheduling Problem
• Activity Selection Problem
• Huffman Coding
• Optimal Storage on Tapes
• Optimal Merge Pattern
• Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm

---

Additional Reading: Wiki