Home » Interview coding problems/challenges

Activity Selection Problem

Here, we are going to learn about the solution of activity selection problem and its C++ implementation.
Submitted by Divyansh Jaipuriyar, on August 16, 2020

Problem statement

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.

Problem description

You are required to generate a maximum number of activities that a single person can do keeping in mind that the next job can only be started if the start time of the next job is greater than the finish time of the previous job. So you are required to use some logic to develop some algorithms such that you get the maximum value of the jobs that can be performed.

Note: The start time and end time of two activities may coincide.

Input

The first line contains T denoting the number of testcases. Then follows description of testcases. First line is N number of activities then second line contains N numbers which are starting time of activities. Third line contains N finishing time of activities.

Output

For each test case, output a single number denoting maximum activities which can be performed in new line.

Examples

Input:
T=1
N=7
3 5
1 3
0 6
5 7
3 8
12 14
8 11

Output:
4, 
as (1 4)-> (5 7) ->(8 11) -> (12 14) is the order 
in which we can get maximum number of activities 
that can be performed by single person.

Solution Approach

The problem is a variation of standard longest increasing subsequence problem, we will store the pair start time and end time in a vector and sort the given vector in increasing order of their finish time, we will create a LIS[] array which will store the length of longest increasing subsequence (jobs that are not intersecting each other) till index length id.

Initially, we can fill all the elements of the LIS[] for the given problem since we can always assign 1 activity to one person.

Iterate through all index from 1 to n-1 since indexing starts from 0.

It can be defined as LIS[i]=max(LIS[i],LIS[j]+1),(j<i && i<n and activities[j].end<=activities[i].start)

otherwise

LIS[i]=1 if only that element does not follow above equation.

Time Complexity for the above approach in the worst case is: O(n*n)
Space complexity for the above approach in the worst case is: O(n*n)

C++ Implementation

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

typedef long long ll;

//boolean function which will
//return true if according
//to finish time of given vector.
bool orderbysec(const pair<ll, ll>& p1, const pair<ll, ll>& p2)
{
    //if p1 has smaller finish time
    //then return true.
    if (p1.second < p2.second)
        return true;
    else
        return false;
}

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter number of activities: ";
        ll n;
        cin >> n;

        ll x, y;
        vector<pair<ll, ll> > vp;

        cout << "Enter start and finish time:\n";
        for (ll i = 0; i < n; i++) {
            cin >> x >> y;
            vp.push_back({ x, y });
        }

        //sort given vector according
        //to finish time element
        sort(vp.begin(), vp.end(), orderbysec);

        //create LIS vector.
        vector<ll> LIS(n, 1);
        for (ll i = 1; i < n; i++) {
            for (ll j = 0; j < i; j++) {
                if (vp[i].first >= vp[j].second and LIS[i] < LIS[j] + 1)
                    LIS[i] = LIS[j] + 1;
            }
        }
        //print maximum value of LIS
        //vector that will print the maximum
        //activities that single person can perform
        cout << *max_element(LIS.begin(), LIS.end()) << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 2
Enter number of activities: 6
Enter start and finish time:
1 2
3 4
2 6
5 7
8 9
5 9
4
Enter number of activities: 4
Enter start and finish time:
1 2
3 4
2 3
5 6
4