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

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-05-01

229

Print Maximum Length Chain of Pairs

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

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-05-01

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

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,

We have to sort N pairs with their first element and take a new array of length equals N.
We will put one in every index of the array.
We start with the second element and traverse through the whole set of pairs.
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)).
Repeat step 4 through the whole traversal.
After that, we traverse the whole array and take the maximum value.

To print the chains, we follow this approach,

Store the index of the maximum value and take a vector.
Insert the pair at the index equals the index of the max value.
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

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

total answers (1)