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-

#include <cstdio>
#include <algorithm>
using namespace std;

pair< int, int > a[100000];

//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;
}

2 comments on “Activity Selection Problem

  1. NIKHIL KUMAR SINGH on said:

    Thanks for the implementation .. It was awesome

  2. tanjan on said:

    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[0] – 7, a.second[0] – 1 // i = 0, whereas activity task index = 0
    a.first[1] – 8, a.second[1] – 1 // i = 1, whereas activity task index = 3
    a.first[2] – 8, a.second[2] – 5 // i = 2, whereas activity task index = 1
    a.first[3] – 8, a.second[3] – 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!

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,728 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>