What is the activity selection problem?

The activity selection problem is an optimization problem used to find the maximum number of activities a person can perform if they can only work on one activity at a time. This problem is also known as the interval scheduling maximization problem (ISMP).

The greedy algorithm provides a simple, well-designed method for selecting the maximum number of non-conflicting activities.

Greedy is an algorithmic paradigm that builds up a solution piece by piece. It always chooses the next piece that offers the most obvious and immediate benefit.

Algorithm

We are provided with n activities; each activity has its own start and finish time. In order to find the maximum number of non-conflicting activities, the following steps need to be taken:

Sort the activities in ascending order based on their finish times.
Select the first activity from this sorted list.
Select a new activity from the list if its start time is greater than or equal to the finish time of the previously selected activity.
Repeat the last step until all activities in the sorted list are checked.

#include <stdio.h>
void activitySelection(int s[], int f[], int n) {
  int temp_start, temp_finish;
  //step 1
  //Sort the activities based on their finish times in ascending order.
  for(int i = 1; i < n; i++) {
    for(int j = 0; j < n - 1; j++){
      if(f[j] > f[j+1]) {
        temp_start = s[j];
        temp_finish = f[j];
        f[j] = f[j+1];
        s[j] = s[j+1];
        f[j+1] = temp_finish;
        s[j+1] = temp_start;
      }
    }
  }
  //sorted
  printf("Sorted activities in ascending order of Finish time \n");
  for(int i = 0; i < n; i++) {
    printf("%10i %10i\n", s[i], f[i]);
  }
  //step 2
  //select the first activity
  printf("Maximum Selected Activities \n");
  printf("%10s  %10s \n", "Start", "Finish");
  printf("%10i %10i \n", s[0], f[0]);
  //step 3
  //Select a new activity from the list if its `start` time
  // is greater than or equal to the `finish` time of the 
  // previously selected activity.
  int i = 0;
  for(int j = 1; j < n; j++) {
    if(s[j] >= f[i]) {
      printf("%10i %10i \n", s[j], f[j]);
      i = j;
    }
  }
}
int main(void) {
  int start[] =  {5, 1, 0, 3, 5, 8}; 
  int finish[] =  {9, 2, 6, 4, 7, 9}; 
  int n = 6; 
  activitySelection(start, finish, n);
  return 0;
}

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is the activity selection problem?

Algorithm

Implementation