# 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.

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 lengthid.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

1ton-1since 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]=1if only that element does not follow above equation.Time Complexityfor the above approach in the worst case is:O(n*n)Space complexityfor the above approach in the worst case is:O(n*n)C++ Implementation

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