Home » Interview coding problems/challenges

Print Maximum Length Chain of Pairs

Here, we are going to find the solution to print maximum length chain of pairs using dynamic programming approach.
Submitted by Souvik Saha, on June 28, 2020

Problem statement

An N pair array is given to you. In every pair, the first number is always smaller than the second number. A pair (a,b) can follow another pair (c,d) if a is greater than d. Two pairs are joined with this logic. Your task is to join this set of pairs and print the pairs of the chain.

Input:
T-test cases.
N no. of pairs are given.

E.g.
3

8
4 5 6 9 1 2 15 26 7 8 10 17 5 9 8 17

6
5 8 11 15 6 10 12 17 11 14 15 16

2
2 10 6 12

Output:
Print pairs of the chain.

Example

T = 3

Input:
8
4 5 6 9 1 2 15 26 7 8 10 17 5 9 8 17
Output:
1 2 4 5 7 8 15 26 

Input:
6
5 8 11 15 6 10 12 17 11 14 15 16
Output:
6 10 11 14 15 16

Input:
2
2 10 6 12
Output:
6 12 

Explanation with example:

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 i^th 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