# Activity Selection Problem

### Greedy Algorithm

Share

In this video we will learn about Activity Selection Problem, a greedy way to find the maximum number of activities a person or machine can perform, assuming that the person or machine involved can only work on a single activity at a time.

## Points to remember

• For this algorithm we have a list of activities with their starting time and finishing time.
• Our goal is to select maximum number of non-conflicting activities that can be performed by a person or a machine, assuming that the person or machine involved can work on a single activity at a time.
• Any two activities are said to be non-conflicting if starting time of one activity is greater than or equal to the finishing time of the other activity.
• In order to solve this problem we first sort the activities as per their finishing time in ascending order.
• Then we select non-conflicting activities.

## Problem

Consider the following 8 activities with their starting and finishing time.

 Activity a1 a2 a3 a4 a5 a6 a7 a8 start 1 0 1 4 2 5 3 4 finish 3 4 2 6 9 8 5 5

Our goal is to find non-conflicting activities.

For this we follow the given steps

1. sort the activities as per finishing time in ascending order
2. select the first activity
3. select the new activity if its starting time is greater than or equal to the previously selected activity
REPEAT step 3 till all activities are checked

Step 1: sort the activities as per finishing time in ascending order

 Sorted Activity a3 a1 a2 a7 a8 a4 a6 a5 start 1 1 0 3 4 4 5 2 finish 2 3 4 5 5 6 8 9

Step 2: select the first activity

Step 3: select next activity whose start time is greater thanâ€¨or equal to the finish time of the previously selected activity

## Pseudo Code

``````
Set i = 0;    //pointing at first element
for j = 1 to n-1 do
if start time of j >= finish time of i then
Print j
Set i = j

endif

endfor
``````

## Code in C

``````
#include <stdio.h>

struct Activity {
char id[5];
int start;
int finish;
};

void activitySelection(Activity activities[], int n);

int main(void) {

//activities
Activity activities[8] = {
{"a1", 1, 3},
{"a2", 0, 4},
{"a3", 1, 2},
{"a4", 4, 6},
{"a5", 2, 9},
{"a6", 5, 8},
{"a7", 3, 5},
{"a8", 4, 5}
};

//number of activities
int n = 8;

activitySelection(activities, n);

return 0;
}

void activitySelection(Activity activities[], int n) {
//variables
int i, j;

Activity temp;

//step 1
//sort the activities as per finishing time in ascending order
for(i = 1; i < n; i++) {
for(j = 0; j < n - 1; j++){
if(activities[j].finish > activities[j+1].finish) {
temp = activities[j];
activities[j] = activities[j+1];
activities[j+1] = temp;
}
}
}

//sorted
printf("Sorted activities as per finish time (ascending order)\n");
printf("%10s %10s %10s\n", "Activity", "Start", "Finish");
for(i = 0; i < n; i++) {
printf("%10s %10i %10i\n", activities[i].id, activities[i].start, activities[i].finish);
}

//step 2
//select the first activity
printf("-----Selected Activities-----\n");
printf("%10s %10s %10s\n", "Activity", "Start", "Finish");
printf("%10s %10i %10i\n", activities[0].id, activities[0].start, activities[0].finish);

//step 3
//select next activity whose start time is greater than
//or equal to the finish time of the previously selected activity
i = 0;
for(j = 1; j < n; j++) {
if(activities[j].start >= activities[i].finish) {
printf("%10s %10i %10i\n", activities[j].id, activities[j].start, activities[j].finish);
i = j;
}
}
}
``````

## Output

``````
Sorted activities as per finish time (ascending order)
Activity      Start     Finish
a3          1          2
a1          1          3
a2          0          4
a7          3          5
a8          4          5
a4          4          6
a6          5          8
a5          2          9
-----Selected Activities-----
Activity      Start     Finish
a3          1          2
a7          3          5
a6          5          8

``````
Share