# 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
_{1}, a_{2}, a_{3}, .. 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
_{1}, A_{3}} and {A_{2}, A_{3}} 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
_{1}≤ f_{2}≤ f_{3}≤ . . . ≤ 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
_{1}, A_{2}, A_{3}, A_{4}, A_{5, }A_{6}, A_{7}, A_{8}, A_{9}}, 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_{4}for scheduling, we will end up with two activities {A_{4}, A_{7}}. - If we select A
_{1}followed by A_{6}, we end up with {A_{1}, A_{6}} only. - Whereas, greedy algorithm schedules {A
_{1}, A_{2}, A_{3}, A_{7}}, 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 **f_{i} ≤ s_{i} **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
^{2}) time. - Sorting of activities by their finishing time takes O(n.log
_{2}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_{2}n) = O(nlog_{2}n)

## Example

**Example: Given following data, determine the optimal schedule using greedy approach. A = <A _{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}>, 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 | A_{1} | A_{3} | A_{4} | A_{2} | A_{5} | A_{6} |

f_{i} | 3 | 4 | 5 | 6 | 7 | 9 |

s_{i} | 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_{1} is already selected, so S = < A_{1}>

f_{1} > s_{2}, so A_{1} and A_{2} are not compatible. Do check for next activity

f_{1} ≤ s_{3}, so A_{1} and A_{3} are compatible. Schedule A_{3}, S = <A_{1}, A_{3}>

f_{3} ≤ s_{4}, so A_{3} and A_{4} are compatible. Schedule A_{4}, S = <A_{1}, A_{3}, A_{4}>

f_{4} ≤ s_{5}, so A_{4} and A_{5} are compatible. Schedule A_{5}, S = <A_{1}, A_{3}, A_{4}, A_{5}>

f_{5} > s_{6}, so A_{5} and A_{6} are not compatible. And there is no more activity left to check. Hence final schedule is, S = <A_{1}, A_{3}, A_{4}, A_{5}>

**Example: Given following data, determine the optimal schedule for activity selection using greedy algorithm. A = <A _{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}, A_{7}, A_{8}>, 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 | A_{2} | A_{1} | A_{4} | A_{5} | A_{3} | A_{6} | A_{8} | A_{7} |

f_{i} | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

s_{i} | 2 | 1 | 4 | 5 | 3 | 6 | 8 | 7 |

A_{2} is already selected, so S = < A_{2}>

f_{2} > s_{1}, so A_{1} and A_{2} are not compatible. Do check for next activity

f_{2} ≤ s_{4}, so A_{2} and A_{4} are compatible. Schedule A_{3}, S = <A_{2}, A_{4}>

f_{4} ≤ s_{5}, so A_{4} and A_{5} are compatible. Schedule A_{5}, S = <A_{2}, A_{4}, A_{5}>

f_{5} > s_{3}, so A_{3} and A_{5} are not compatible. Do check for next activity

f_{5} ≤ s_{6}, so A_{5} and A_{6} are compatible. Schedule A_{6}, S = <A_{2}, A_{4}, A_{5}, A_{6}>

f_{6} ≤ s_{8}, so A_{6} and A_{6} are compatible. Schedule A_{8}, S = <A_{2}, A_{4}, A_{5}, A_{6}, A_{8}>

f_{8} > s_{7}, so A_{8} and A_{7} are not compatible. And there is no more activity left to check.

So final schedule is, S = <A_{2}, A_{4}, A_{5}, A_{6}, A_{8}>

## 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