To print the longest chain from N pairs is a problem of combination and permutation. If we go with the recursive approach then it will take a long time.

let f(i) = maximum chain length among ith pairs.

To solve this problem, we will follow these steps,

1. We have to sort N pairs with their first element and take a new array of length equals N.
2. We will put one in every index of the array.
3. We start with the second element and traverse through the whole set of pairs.
4. Every time we compare the current element with the elements that are ahead of it and take those elements having the second element is smaller than it.
   f(current element)=max(f(current element), f(element having the second element is smaller than it)).
5. Repeat step 4 through the whole traversal.
6. After that, we traverse the whole array and take the maximum value.

To print the chains, we follow this approach,

1. Store the index of the maximum value and take a vector.
2. Insert the pair at the index equals the index of the max value.
3. Traverse the new array from the store index to the beginning and take those indexes where the value of the new array is small by 1 and the second element of the pair is less the first element of the inserted pair.

C++ Implementation:

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

struct val {
    int first;
    int second;
};

void maxChainLen(struct val p[], int n);

int main()
{
    int t;
 
    cout << "TestCase : ";
    cin >> t;
 
    while (t--) {
        int n;
 
        cout << "Enter number of pair : ";
        cin >> n;
 
        val p[n];
 
        cout << "Enter the pairs : ";
        for (int i = 0; i < n; i++) {
            cin >> p[i].first >> p[i].second;
        }

        cout << "Max chain length : ";
        maxChainLen(p, n);
    }
    return 0;
}

void swap(struct val& p1, struct val& p2)
{
    struct val temp = p1;
    p1 = p2;
    p2 = temp;
}

void heapify(struct val* p, int i, int n)
{
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int low = i;
    if (l < n && p[l].first > p[low].first)
        low = l;
    if (r < n && p[r].first > p[low].first)
        low = r;
    if (low != i) {
        swap(p[low], p[i]);
        heapify(p, low, n);
    }
}

void sort(struct val* p, int n)
{
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(p, i, n);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(p[i], p[0]);
        heapify(p, 0, i);
    }
}

void print_chain(struct val p[], int* arr, int n, int val)
{
    int ind = 0;
    for (int i = 0; i < n; i++) {
        if (val == arr[i]) {
            ind = i;
        }
    }
    vector<struct val> v;
    v.push_back(p[ind]);
    int prev = arr[ind];
    for (int i = n - 1; i >= 0; i--) {
        if (prev == 1) {
            break;
        }
        if (arr[i] + 1 == prev && p[i].second < v[v.size() - 1].first) {
            v.push_back(p[i]);
            prev = arr[i];
        }
    }
    for (int i = v.size() - 1; i >= 0; i--) {
        cout << v[i].first << " " << v[i].second << " ";
    }
    cout << endl;
}

void maxChainLen(struct val p[], int n)
{
    sort(p, n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        arr[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (p[i].first > p[j].second) {
                arr[i] = max(arr[i], arr[j] + 1);
            }
        }
    }
    print_chain(p, arr, n, arr[n - 1]);
}

Output

TestCase : 3
Enter number of pair : 8
Enter the pairs : 4 5 6 9 1 2 15 26 7 8 10 17 5 9 8 17
Max chain length : 1 2 4 5 7 8 15 26 
Enter number of pair : 6
Enter the pairs : 5 8 11 15 6 10 12 17 11 14 15 16
Max chain length : 6 10 11 14 15 16 
Enter number of pair : 2
Enter the pairs : 2 10 6 12
Max chain length : 6 12