Activity Scheduling Problem

Apply the Greedy approach to perform selection of different activities according to some constraints.

We'll cover the following

Problem statement

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.

Let us take the following example: Consider the following 3 activities sorted by finish time:

start[] = {10, 12, 20}

finish[] = {20, 25, 30}

A person can perform at most two activities. The maximum set of activities that can be executed is {0, 2} (These are indexes in start[] and finish[]).

Solution: Greedy approach

The Greedy choice is to always pick the next activity whose finish time is the least among the remaining activities and whose start time is more than or equal to the finish time of the previously selected activity. We can sort the activities according to their finishing time to always consider the next activity as the minimum finishing time activity.

Let us now move on to the implementation.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool cmp(pair<int, int> I, pair<int,int> r){
    return I.second <r.second;
}
int main()
{
    int res = 1;
    vector<pair<int,int> > activity = {{10,20},{12,25},{20,30}};
    sort(activity.begin(),activity.end(),cmp); 
    int fin = activity[0].second;
    for(int i = 1; i < activity.size(); i++)
    {
        if(activity[i].first >= fin)
        {
            fin = activity[i].second;
            res++;
        }
    }
    cout << res;
    return 0;
}

Explanation:

  • On line 6, we define a comparator function that will be passed to the built-in sort() function to sort the vector based on the second value of the pair.
  • On line 11, we define our result.
  • On line 12, we create a vector of pairs activity. It means that each element of the vector is a pair that contains the start and finish time of each activity.
  • On line 14, we first sort the activities according to their finish time by using our comparator function.
  • On line 16, we assign a value to fin, which denotes the finish time of the chosen activity, i.e., the activity with the least finish time.
  • On line 18, we run a loop to process all the activities.
  • On line 21, we try to find the first activity whose start time is more than the previous activity’s finish time.
  • On line 23, if we find that activity, then we update our finish time with the finish time of the next activity.
  • On line 24, we increment our result since we have chosen one activity.
  • On line 27, we print our final result.