Activity Selection Problem

By | September 11, 2015

Problem :

You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

This is the most basic example of Greedy Approach.

Greedy Choice Property: Pick/select the activity whose finish time is minimum among all the remaining activities and its start time is greater or equal to the finish time of previously selected activity.

Algorithm:

  1. Sort all the activities in increasing order of their Finish times (Pair-wise sorting of Start and Finish time is required)
  2. Select the first activity and print it.
  3. For all remaining activities,
    1. if the start time is greater than or equal to the finish time of previous activity, then print it,
    2. Else leave that activity and move on in the list.

In the code below, we assume that the activities are already sorted in the increasing order of their finish times.

Here is the working code:

#include<bits/stdc++.h>
using namespace std;

/*The start[] and fin[] array are used to store the starts 
and finish times of the activites resp. */

/*This function Prints the Index of the activities selected*/
void ActivitySelection(int start[], int fin[], int size)
{
    int PresentActivity, j;
    cout<<"The Activities Selected are as follows:\n";
    
    // The first activity always gets selected
    PresentActivity = 0;
    cout<<PresentActivity<<" ";
 
    // Consider rest of the activities
    for (j = 1; j < size; j++)
    {
      /* If this activity has start time greater than or equal to the finish
       time of previously selected activity, then select it */
      if (start[j] >= fin[PresentActivity])
      {
          cout<<j<<" ";
          PresentActivity = j;
      }
    }
}
 
// driver program to test above function
int main()
{
    int start[] =  {4 ,5 ,7 ,8 ,0 ,4 };
    int fin[] =  {5 ,7 ,9 ,9 ,10 ,10 };
    int size = sizeof(start)/sizeof(start[0]);
    ActivitySelection(start, fin, size);
    
    return 0;
}

Time Complexity: O(N) without sorting, O(NlogN)  with sorting included.

Output:

The Activities Selected are as follows:
0 1 2

The assumptions that we took, that the arrays are already sorted, may not be already given in that case, you need to do either of the following 3 things:

  1. Modify sorting algorithm to sort Start[] and finish[] array so that corresponding updations are made in both the arrays.
  2. Make structure and use STL sort, with user define compare function.
  3. Make a Vector of Pairs, with first element as the finish time, and second element as the starting time of the activity. In this method STL sort can be used, without any user defined compare function.

An application of this algorithm is the Spoj BUSYMAN question. Here we use the the 3rd approach mentioned above to solve it. To understand how STL solution works, read the question and then refer to Spoj BUSYMAN solution.