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