# An activity selection problem

The activity selection problem is a mathematical optimization problem. That concerning the selection of non-conflicting activities. Each activity assigned by a start time (si) and finish time (fi). The activity selection problem is to select the maximum number of activities that can be performed by a single machine, assuming that a machine can only work on a single activity at a time.### GREEDY ACTIVITY SELECTOR Algorithm

GREEDY-ACTIVITY-SELECTOR(s, f) 1. n ← length[s] 2. A ← {a1} 3. i ← 1 4. for m ← 2 to n 5. do if sm ≥ fi 6. then A ← A U {am} 7. i ← m 8. return A

### Example

Start time (si) | finish time (fi) | Activity name |
---|---|---|

1 | 4 | A1 |

3 | 5 | A2 |

0 | 6 | A3 |

5 | 7 | A4 |

3 | 9 | A5 |

5 | 9 | A6 |

6 | 10 | A7 |

8 | 11 | A8 |

8 | 12 | A9 |

2 | 14 | A10 |

12 | 16 | A11 |

Selected Activities are:

**A1, A4, A8, A11**

### activity selection problem in c

#include<stdio.h> #include<conio.h> void activities(int s[], int f[], int n) { int i, j; printf ("Selected Activities are:\n"); i = 1; printf("A%d ", i); for (j = 1; j < n; j++) { if (s[j] >= f[i]) { printf ("A%d ", j+1); i = j; } } } void main() { int s[] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; int f[] = {4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16}; int n = sizeof(s)/sizeof(s[0]); clrscr(); activities(s, f, n); getchar(); getch(); }