# ACTIVITY SELECTION PROBLEM

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.

### 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.

#### 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 Time | Finish Time | Activity Name |

5 | 9 | A1 |

1 | 2 | A2 |

3 | 4 | A3 |

0 | 6 | A4 |

5 | 7 | A5 |

8 | 9 | A6 |

TABLE AFTER SORTING ACCORDING FINISH TIME

INDEX | START TIME | FINISH TIME | ACTIVITY NAME | SELECTION |

1 | 1 | 2 | A2 | 0 |

2 | 3 | 4 | A3 | 0 |

3 | 0 | 6 | A4 | 0 |

4 | 5 | 7 | A5 | 0 |

5 | 5 | 9 | A1 | 0 |

6 | 8 | 9 | A6 | 0 |

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

SELECTION OF ACTIVITIES

INDEX | START TIME | FINISH TIME | ACTIVITY NAME | SELECTION |

1 | 1 | 2 | A2 | 1 |

2 | 3 | 4 | A3 | 1 |

3 | 0 | 6 | A4 | 0 |

4 | 5 | 7 | A5 | 1 |

5 | 5 | 9 | A1 | 0 |

6 | 8 | 9 | A6 | 1 |

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.

- Solve the given activity selection problem

The sequence of activity is……………… - 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………………………. - 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: