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

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.

1. Sort the activities in Activity[] according to their finishing time in the ascending order.
2. Select the first activity from sorted Activity[] and append the soltuion to Solution[].
3. 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[].
4. 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.

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)