# Activity Selection Problem

Activity selection problem is an example of greedy algorithm.Greedy algorithms look for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step will provide the most obvious benefit.The advantage of using a greedy algorithm is that solutions to smaller sub-problems of the problem can be straightforward and easy to understand.The disadvantage is that it is entirely possible that the most optimal short-term solutions may lead to the worst long-term outcome.

Problem-

Given n activities with their start and finish times,we have to find 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.

Algorithm-

1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do following for remaining activities in the sorted array.
a) If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it.

Example-

start[]={1,5,7,1}

finish[]={7,8,8,8}

The maximum set of activities that can be executed by a single person is {0,2} where 0,2 are the activity numbers.

start[] = {1, 3, 0, 5, 8, 5}

finish[] = {2, 4, 6, 7, 9, 9}

The maximum set of activities that can be executed by a single person is {0, 1, 3, 4}.

Code-

[cpp]
#include <cstdio>
#include <algorithm>
using namespace std;

pair< int, int > a;

//a[].first denotes the finish time
//a[].second denotes the starting time

int main()
{
int i, n, last;

//n denotes the number of activities

scanf("%d", &n);

for(i = 0; i < n; i++)
{
scanf("%d %d",&a[i].second,&a[i].first);
}
//using sort function for an array of pairs sorts
// it according to the first one.
//sorting according to finish time
sort(a, a + n);

last = -1;//initialization
for(i = 0; i < n; i++)
{
if(a[i].second>= last) //step 3
{
//printing the activity number which is selected
printf("%d ",i);
last = a[i].first;
}
}

return 0;
}

[/cpp] saurabh

1. NIKHIL KUMAR SINGH says:

Thanks for the implementation .. It was awesome

2. tanjan says:

The index of activity gets messed up.
For example, given the data –
start[]={1,5,7,1}
finish[]={7,8,8,8}

Here, the output gives 0 3, where it should’ve been 0 2, which is because when the pair is sorted according to the given finish array, the data becomes like this-
i starting from 0, i++;
a.first – 7, a.second – 1 // i = 0, whereas activity task index = 0
a.first – 8, a.second – 1 // i = 1, whereas activity task index = 3
a.first – 8, a.second – 5 // i = 2, whereas activity task index = 1
a.first – 8, a.second – 7 // i = 3, whereas activity task index = 2

Which consequently gives out the answer 0, 3; the value of i, where it really should have been 0, 2; the value of activity task index.
That means we have to keep track of the activity task index. I have tried but failed to keep track. Can you provide a method which can do that?
Thanks!