ACTIVITY SELECTION PROBLEM

Activity selection problem

Activity selection problem through the greedy approach. Here covers, Introduction, Greedy approach, Solving Steps, Example, Algorithm, C program, Time complexity, Real life application.

In this “ACTIVITY SELECTION PROBLEM” article, you can learn the Activity selection problem through the greedy approach. Here covers, Introduction, Greedy approach, Solving Steps, Example, Algorithm, C program, Time complexity, Real life application.

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. The greedy technique is used for finding the solution since this is an optimization problem. We will use the greedy approach to find the next activity whose finish time is minimum among rest activities, and the start time is more than or equal to the finish time of the last selected activity.

WHAT IS ACTIVITY SELECTION PROBLEM?

Let’s consider that you have n activities with their start and finish times, The objective is to find solutions set having the 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.

EXAMPLE OF ACTIVITY SELECTION PROBLEM
EXAMPLE OF ACTIVITY SELECTION PROBLEM

SOME POINTS

It might be possible to complete all the activities since their timing 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 refers to the finishing time of the activities i and j respectively.

GREEDY APPROACH

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.

ACTIVITY SELECTION PROBLEM
ACTIVITY SELECTION PROBLEM

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.

OUTPUT DATA FOR THE ALGORITHM

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

STEPS FOR ACTIVITY SELECTION PROBLEM

Step 1: Sort the given activities in ascending order according to their finishing time.
Step 2: Select the first activity from the sorted array act[] and add it to the 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 the previously selected activity, then add it to the sol[] array.
Step 5: Select the next activity in the act[] array.
Step 6: Print the sol[] array.

EXAMPLE :

Start TimeFinish TimeActivity Name
59A1
12A2
34A3
06A4
57A5
89A6
EXAMPLE OF ACTIVITY SELECTION PROBLEM

TABLE AFTER SORTING ACCORDING FINISH TIME

INDEXSTART TIMEFINISH TIMEACTIVITY NAMESELECTION
112A20
234A30
306A40
457A50
559A10
689A60
TABLE AFTER SORTING ACCORDING FINISH TIME

In the above table, Selection is not done. Given below table is shown the selected activities.

SELECTION OF ACTIVITIES

INDEXSTART TIMEFINISH TIMEACTIVITY NAMESELECTION
112A21
234A31
306A40
457A51
559A10
689A61
TABLE AFTER SELECTION OF ACTIVITIES

Here, Solution is given as all selected activities. Thus Solution is {A2, A3, A5, A6}.

ALGORITHM

Begin
Initially sort the given activity list
set i:=1
display the ith activity // in this case, it is the first activity.
for j:=1 to n-1 do
if start time of act[j] > end of act[i] then
display the jth activity
i:=j
done
End

C PROGRAM :

#include<stdio.h>
void activities(int a[],int s[], int f[], int n)
{
int i, j;
printf (“Selected Activities are:\n”);
i = 0;
printf(“A%d “, a[i]);
for (j = 1; j < n; j++) { if (s[j] >= f[i])
{
printf (“A%d “, a[j]);
i = j;
}
}
}
int main()
{
int s[100],f[100],a[100], n, c, d, swap,swap1,swap2;
printf(“Enter number of elements\n”);
scanf(“%d”, &n);
printf(“Enter %d integers of Item Number\n”, n);
for (c = 0; c < n; c++) scanf(“%d”, &a[c]); printf(“Enter %d integers of start time\n”, n); for (c = 0; c < n; c++) scanf(“%d”, &s[c]); printf(“Enter %d integers of end time\n”, n); for (c = 0; c < n; c++) scanf(“%d”, &f[c]); /* Sort by finish time in increasing order */ for (c = 0 ; c < n – 1; c++) { for (d = 0 ; d < n – c – 1; d++) { if (f[d] > f[d+1])
{
swap= s[d];
s[d]= s[d+1];
s[d+1] = swap;
swap1 = f[d];
f[d]= f[d+1];
f[d+1] = swap1;
swap2 = a[d];
a[d]= a[d+1];
a[d+1] = swap2;
}//if
}//d
}//c
activities(a,s, f, n);
return 0;
}

INPUT-OUTPUT:

Enter number of elements
6
Enter 6 integers of Item Number
1
2
3
4
5
6
Enter 6 integers of start time
5
1
3
0
5
8
Enter 6 integers of end time
9
2
4
6
7
9
Selected Activities are:
A2 A3 A5 A6

TIME COMPLEXITY

When activities are sorted by their finish time: O(N)

When activities are not sorted by their finish time, the time complexity is O(N LOG N) due to the complexity of sorting.

REAL LIFE APPLICATIONS OF ACTIVITY SELECTION 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 Operation Research for dealing with real life business problems.

  1. Solve the given activity selection problem
    The sequence of activity is………………
  2. Consider the following 6 activities.Activity [] = {1, 2, 3, 4, 5, 6}
    start [] = {1, 3, 0, 5, 8, 5};
    finish [] = {2, 4, 6, 7, 9, 9};
    The maximum set of activities that can be executed
    by a single person is……………………….
  3. Solve the below activity selection problem in such a way where you can select the maximum number of activities when all activities wish to use the same resource.
    Activity Name: A1, A2, A3, A4, A5, A6
    Start Time (s): 5, 1, 3, 0, 5, 8
    Finish Time (f): 9, 2, 4, 6, 7, 9
    Also, state the kind of algorithm you are used with its complexity.

In this “ACTIVITY SELECTION PROBLEM” article, you can learn the Activity selection problem through the greedy approach. Here covers, Introduction, Greedy approach, Solving Steps, Example, Algorithm, C program, Time complexity, Real life application.

You might like:

C programming note
Shell programming

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami