Activity Selection Problem

In this chapter we shall learn on how to solve activity selection problem with the help of example and using greedy method.

Problem Statement:

You are given list of activity with starting and ending time. Your job is to find the maximum number of activities can be performed by that machine. Note that the machine can only perform 1 task at a time.

These activities should be non-conflicting. It means, a new activity start time should be greater than or equal to the ending time of the previous activity.

For example:

 Below is the list of activity with starting and ending time;

Now you can select activity a1, but you cannot choose a2 because the start time of a2 is less than the ending time of a1. Hence you skip a2 and move to a3.

As a3 starting time is greater than the time of a1, you will choose it. But is the optimal solution? No

Because, if you choose a2, a3. Then you will get more work done.

So how to solve this problem?

We can solve this by greedy method. We follow below 3 steps to arrive at the solution.

Step 1:  Sort the activities according to the finishing time in ascending order.

Step 2: Select that activity

Step 3: Check the new activity start time is greater than or equal to end time of previous activity and select it. Repeat step 2 and 3 till all activities are checked.

Consider the below table:

Now sort the activity according to the end time

Now select a1 and put it in the result table

Now a2 start time is less than a1 end time. Hence skip a2.

Now a6 start time is greater than a1 end time. Hence select that activity.

Similarly, a4 start time is less than a6 end time. Hence discard it.

a3 start time is equal to a6 end time. Hence select that activity.

a5 start time is equal to a3 end time. Hence select it.

Hence the final result.

Solution for activity selection problem in C++

#include <iostream>

using namespace std;

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

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

  Activity temp;

  // sort activities in ascending order according to their 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;
      }
    }
  }

  cout<<"Activities printed according to sorted order of their finishing time."<<endl;
  cout<<"Activity Start Finish"<<endl;

  for(i = 0; i < n; i++) 
  {
    cout<<activities[i].id<<"       "<< activities[i].start<<"       " <<activities[i].finish<<endl;
  }

  cout<<"Final Result"<<endl;
  cout<< "Activity  Start Finish"<<endl;
  cout<< activities[0].id<<"       " << activities[0].start<<"       " <<activities[0].finish<<endl;


  //check and select the next activity whose start time is greater than or equal to the finishing period of previous 
  //activity
  i = 0;
  for(j = 1; j < n; j++) 
  {
    if(activities[j].start >= activities[i].finish) 
    {
      cout<<activities[j].id<<"       "<< activities[j].start<<"       "<< activities[j].finish<<endl;
      i = j;
    }
  }
}
int main(void) {

  Activity activities[8] = 
  {
    {"a1", 2, 3},
    {"a2", 1, 4},
    {"a3", 8, 10},
    {"a4", 6, 9},
    {"a5", 10, 15},
    {"a6", 5, 8},
  };
  int total_activity = 6;

  activitySelection(activities, total_activity);

  return 0;
}

Output:

Activities printed according to sorted order of their finishing time.
Activity Start Finish
a1       2       3
a2       1       4
a6       5       8
a4       6       9
a3       8       10
a5       10       15
Final Result
Activity  Start Finish
a1       2       3
a6       5       8
a3       8       10
a5       10       15