Activity Selection Problem

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.

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

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