Activity Selection Problem

December 30, 2021

Activity Selection Problem

In the activity selection problem, we are given a list of activity or task. We have to compute the maximum number of tasks we can complete. The problem can we solved optimally using greedy algorithm. In this article we will provide C++ solution with an explanation.

Activity Selection Problem Description

Given a list of n activities. Each activity has a start time and an end time. At a time you can only perform one activity. Find the maximum number of activities you can complete.

Input:

First line contains single integer n – the number of activites .
Next n lines contains two integers – the start and end time of ith activity.

Output:

The maximum number of activities that can be performed.

Activity Selection Problem Solution

The problem can be solved using greedy algorithm. Since we have to find maximum number of activities we will always pick an activity which has least ending time possible.

Why? Because picking such activity will maximize our chances of picking another job after this current activity is completed.

Steps –

Sort the activities using in increasing order of their end time.
Pick the first activity.
Iterate on all remaining activities, an activity can be picked or completed if its start time is greater than equal to end time of previous activity.

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
class activity
{
public:
    int st, ed;
};
bool compare(activity A, activity B)
{
    return A.ed < B.ed;
}
int main()
{
    int n;
    cin >> n;

    activity arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i].st >> arr[i].ed;

    sort(arr, arr + n, compare);

    int ct = 0;
    int ed = –1;

    for (int i = 0; i < n; i++)
    {
        if (arr[i].st >= ed)
        {
            ed = arr[i].ed;
            ct++;
        }
    }

    cout << “No of activities = “ << ct << endl;
    return 0;
}

Output

3
1 9
2 5
6 8
No of activities = 2