Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  245 
0

Activity Selection Problem

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.
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
You are given a list of jobs where each job has a ... >>
<< You are standing in some location (x, y) on an isl...