Activity Selection Problem

The Activity Selection Problem is an optimization problem which deals with the selection of non-conflicting activities that needs to be executed by a single person or machine in a given time frame.

Each activity is marked by a start and finish time. Greedy technique is used for finding the solution since this is an optimization problem.

What is Activity Selection Problem?

Let's consider that you have n activities with their start and finish times, the objective is to find solution set having maximum number of non-conflicting activities that can be executed in a single time frame, assuming that only one person or machine is available for execution.

Some points to note here:

• It might not be possible to complete all the activities, since their timings can collapse.
• Two activities, say i and j, are said to be non-conflicting if si >= fj or sj >= fi where si and sj denote the starting time of activities i and j respectively, and fi and fj refer to the finishing time of the activities i and j respectively.
• Greedy approach can be used to find the solution since we want to maximize the count of activities that can be executed. This approach will greedily choose an activity with earliest finish time at every step, thus yielding an optimal solution.

Input Data for the Algorithm:

• act[] array containing all the activities.
• s[] array containing the starting time of all the activities.
• f[] array containing the finishing time of all the activities.

Ouput Data from the Algorithm:

• sol[] array refering to the solution set containing the maximum number of non-conflicting activities.

Steps for Activity Selection Problem

Following are the steps we will be following to solve the activity selection problem,

Step 1: Sort the given activities in ascending order according to their finishing time.

Step 2: Select the first activity from sorted array act[] and add it to sol[] array.

Step 3: Repeat steps 4 and 5 for the remaining activities in act[].

Step 4: If the start time of the currently selected activity is greater than or equal to the finish time of previously selected activity, then add it to the sol[] array.

Step 5: Select the next activity in act[] array.

Step 6: Print the sol[] array.

---

Activity Selection Problem Example

S = (A1 A2 A3 A4 A5 A6 A7 A8 A9 A10)
Si = (1,2,3,4,7,8,9,9,11,12)
fi = (3,5,4,7,10,9,11,13,12,14)



Compute a schedule where the greatest number of activities takes place.




Solution: 




The solution to the above Activity scheduling problem using a greedy strategy is illustrated below:




Arranging the activities in increasing order of end time

















Now, schedule A1




Next schedule A3 as A1 and A3 are non-interfering.




Next skip A2 as it is interfering.




Next, schedule A4 as A1 A3 and A4 are non-interfering, then next, schedule A6 as A1 A3 A4 and A6 are non-interfering.




Skip A5 as it is interfering.




Next, schedule A7 as A1 A3 A4 A6 and A7 are non-interfering.




Next, schedule A9 as A1 A3 A4 A6 A7 and A9 are non-interfering.




Skip A8 as it is interfering.




Next, schedule A10 as A1 A3 A4 A6 A7 A9 and A10 are non-interfering.




Thus the final Activity schedule is: