# Activity selection problem

The **Activity Selection Problem** is an optimization problem which is used to select the maximum number of activities from the set of activities that can be executed in a given time frame by a single person. In the set of activities, each activity has its own starting time and finishing time. Since this problem is an optimization problem so the **Greedy algorithm approach** is used to solve the problem.

## Problem Statement

Given a set of activities with their starting and finishing times. Select the maximum number of activities that a single person has to performed with an assumption that only a single activity is executed by a single person at a time.

## Activity Selection Problem Example

Greedy approach is used to find the solution to maximize the count of activities that are to be execute. Using this approach, activity is choose with an earliest finish time at each step in way to get an optimal solution.

Below is the example of Activity Selection Problem with input- output constraint and the solution for the example.

### Input – Output Data for the Activity selection problem Algorithm

**Activity[] :**This array contains all the activities.**Start_Time[] :**This array contains the starting time of all the activities.**Finish_Time[]:**This array contain the finishing time of all the activities.**Solution[] :**This array is used to store the maximum number of non-conflicting activities.

### Input and Output of the Activity selection problem Example

Consider an activities along with their start and end time as

Activity | Start Time | Finish Time |
---|---|---|

A1 | 1 | 2 |

A2 | 0 | 4 |

A3 | 2 | 9 |

A4 | 4 | 6 |

The maximum set of activities that can be executed by a single person are **[A1, A3]**

### Step to Solve the Activity selection problem Example

Following the steps should be follow in order to solve the activity selection problem.

- Sort the activities in
**Activity[]**according to their finishing time in the ascending order. - Select the first activity from sorted
**Activity[]**and append the soltuion to**Solution[]**. - For the remaining activities in
**Activity[]**, select the next activity from**Activity[]**and If the start time of the activity is greater than or equal to the finish time of previous activity, then append the soltuion to**Solution[]**. - Return the
**Solution[]**

### Solution of the Activity selection problem Example

Solution of the above example using the greedy algorithm approach.

**Step 1:** Sorted activities according to their finishing time in the ascending order.

Activity | Start Time | Finish Time |
---|---|---|

A1 | 1 | 2 |

A2 | 0 | 4 |

A4 | 4 | 6 |

A3 | 2 | 9 |

**Step 2:** Select the first activity **A1** from sorted **Activity[]** and append the activity **A2** to **Solution[]**. Therefore the solution is **Solution = [A1]**

**Step 3:** For all remaining activities, select the next activity from and append it to **Solution[]**, if the start time of the activity is greater than or equal to the finish time of previous activity.

- Select next activity
**A2**

Here**Start_Time[A2] < Finish_Time[A1]**.

Since the start time of**A2**is less than the finish time of**A1**. Thus it cannot be added to the solution.

Therefore the solution is**Solution = [A1]** - Select next activity
**A4**

Here**Start_Time[A4] > Finish_Time[A1]**.

Since the start time of**A4**is greater than the finish time of**A1**. Thus it can be added to the solution.

Therefore the solution is**Solution = [A1, A4]** - Select activity
**A3**

Here**Start_Time[A3] < Finish_Time[A4]**.

Since the start time of**A3**is less than the finish time of**A4**. Thus it cannot be added to the solution.

Therefore the solution is**Solution = [A1, A4]**

**Step 4:** Return the **Solution = [A1, A4]**

## Pseudocode for Activity Selection Problem Algorithm

The algorithm used for solve the Activity Selection Problem is known as Greedy Iterative Activity Selector. Here’s Pseudocode for solving Activity Selection Problem using greedy algorithm approach.

```
Greedy-Iterative-Activity-Selector(Activity, Start_Time, Finish_Time):
// length of Activity[]
n = Activity.length
// Sort Activity accoding to finish times
Activity = sorted(Activity)
Solution = []
// append the fisrt activity from Activity[]
Solution.append(Activity[0])
// previous activity Number
prev = 0
// iterate all activity and
// check for condition
for i = 2 to n:
if Start_Time[i] ≥ Finish_Time[pre]:
Solution.append(Activity[i])
prev = i
return Solution[]
```

## Implementation of Activity selection problem Algorithm in Python

```
# function to sort the Activity accoding to finish times
def Sort_activities():
Arr = []
# Calculate the number of activities
N = len(Finish_Time)
for i in range(N):
Arr.append([Finish_Time[i], Activity[i] , Start_Time[i]])
# sort the array
Arr.sort()
for i in range(N):
Finish_Time[i], Activity[i] , Start_Time[i] = Arr[i]
# Function to find the solution to maximize the count
# of activities that are to be execute.
def Greedy_Iterative_Activity_Selector(Activity , Start_Time , Finish_Time ):
# To store the activities
Solution = []
# Append the first activity
Solution.append(Activity[0])
# To store the index of the previous activity
prev = 0
# Calculate the number of activities
N = len(Finish_Time)
# Selection of the remaining activities
for nxt in range(N):
# If the start time of the activity is
# greater than or equal to the finish time
# of previous activity
if Start_Time[nxt] >= Finish_Time[prev]:
# Append the solution if true
Solution.append(Activity[nxt])
# update the prev index
prev = nxt
return Solution
# Main function
if __name__ == "__main__":
# Set of activities with starting time
# and finishing time
Activity = ['A1', 'A2', 'A3', 'A4']
Start_Time = [1 , 0 , 2 , 4]
Finish_Time = [2 , 4 , 9 , 6]
# call function to sort the Activity
Sort_activities()
# Calling function Greedy_Iterative_Activity_Selector
# to get the solution
Solution = Greedy_Iterative_Activity_Selector(Activity,
Start_Time , Finish_Time)
# Printing the solution
print(Solution)
```