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.

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: Output Data from the Algorithm:
• act[] array containing all the activities. • sol[] array referring to the solution set
• s[] array containing the starting time of containing the maximum number of non-
all the activities. conflicting activities.
• f[] array containing the finishing time
of all the 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 A1 A2 A3 A4 A5 A6
Start 5 1 3 0 5 8
Finish 9 2 4 6 7 9

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

Activity A2 A3 A4 A5 A1 A6
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9

Step 2: Select the first activity from sorted array and add it to the solution array,
thus solution = {A2}.
Step 2: Select activity A3. Since the start time of A3 is greater than the finish time
of A2 (i.e. s(A3) > f(A2)), we add A3 to the solution set. Thus sol = {A2, A3}

Activity A2 A3 A4 A5 A1 A6
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9

Step 3: Select A4. Since s(A4) < f(A3), it is not added to the solution set.
Activity A2 A3 A4 A5 A1 A6
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9
 Step 4: Select A5. Since s(A5) > f(A3), A5 gets added to solution set.
Thus sol = {A2, A3, A5}
Activity A2 A3 A4 A5 A1 A6
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9

Step 5: Select A1. Since s(A1) < f(A5), A1 is not added to the solution set.

Activity A2 A3 A4 A5 A1 A6
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9

Step 6: Select A6. A6 is added to the solution set since s(A6) > f(A5).
Thus sol = {A2, A3, A5, A6}.

Activity A2 A3 A4 A5 A1 A6
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9
So Output is:
(1,2) (3,4) (5,7) (8,9)
void printMaxActivities(int s[], int f[], int n)
{
int i, j;

printf(“Following activities are selected\n “);

i = 0;
printf(“\t%d “,i);
for (j = 1; j < n; j++)
{
if (s[j] >= f[i])
{
printf(“\t%d”, j);
i = j;
}
}
}
Time Complexity:

Case 1 : O(N), in case, the given array is sorted according to their finish times,
where N is total steps.

Case 2 : O(NlogN), in case, the given array is not sorted according to their
finish times, where N is total steps.

Space Complexity: O(1), since no extra space is used.

Real-life Applications of Activity Selection Problem

Following are some of the real-life applications of this problem:

• Scheduling multiple competing events in a room, such that each event has its own start
and end time.
• Scheduling manufacturing of multiple products on the same machine, such that each
product has its own production timelines.
• Activity Selection is one of the most well-known generic problems used in Operations
Research for dealing with real-life business problems.
 Activity A1 A2 A3 A4 A5 A6
Q1
Start 0 3 1 5 5 8
Finish 6 4 2 9 7 9

Q2 Input: start[] = [1, 3, 0, 5, 8, 5]

finish[] = [2, 4, 6, 7, 9, 9]

Q3 Input: start[] = [1, 3, 2, 0, 5, 8, 11]

finish[] = [3, 4, 5, 7, 9, 10, 12]

Q4 {1,2} {4,4} {5,10} {9,10} {7,8} {2,4}