Greedy Algorithm

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.

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

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

- sort the activities as per finishing time in ascending order
- select the first activity
- 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

```
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
```

```
#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;
}
}
}
```

```
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
```

ADVERTISEMENT