जोड़ियों की सबसे लंबी चेन

जोड़ियों की एक चेन दी गई है। प्रत्येक जोड़ी में दो पूर्णांक होते हैं और पहला पूर्णांक हमेशा छोटा होता है, और दूसरा बड़ा होता है, यही नियम चेन निर्माण पर भी लागू होता है। एक जोड़ी (x, y) को जोड़ी (p, q) के बाद तभी जोड़ा जा सकता है जब q < x हो।

इस समस्या को हल करने के लिए, सबसे पहले हमें दिए गए जोड़ियों को पहले तत्व के बढ़ते क्रम में सॉर्ट करना होगा। उसके बाद, हम एक जोड़ी के दूसरे तत्व की तुलना अगली जोड़ी के पहले तत्व से करेंगे।

इनपुट और आउटपुट

इनपुट: संख्या जोड़ियों की एक चेन
{(5, 24), (15, 25), (27, 40), (50, 60)}

आउटपुट: दिए गए मानदंड के अनुसार चेन की सबसे बड़ी लंबाई। यहां लंबाई 3 है।

एल्गोरिदम

maxChainLength(arr, n)

चेन का प्रत्येक तत्व दो तत्व a और b रखेगा

इनपुट: जोड़ियों का ऐरे, ऐरे में आइटम्स की संख्या
आउटपुट: अधिकतम लंबाई

शुरुआत
    maxChainLen ऐरे को आकार n का परिभाषित करें, और 1 से भरें
    max := 0
    i := 1 से n तक, करें
        j := 0 से i-1 तक, करें
            यदि arr[i].a > arr[j].b और maxChainLen[i] < maxChainLen[j] + 1, तो
                maxChainLen[i] := maxChainLen[j] + 1
        पूर्ण
    पूर्ण
    max := maxChainLen ऐरे में अधिकतम लंबाई
    वापस max
अंत

उदाहरण (C++ कोड)

#include <iostream>
#include <algorithm>
using namespace std;

struct numPair {
    int a;
    int b;
};

int maxChainLength(numPair arr[], int n) {
    int max = 0;
    int *maxChainLen = new int[n];
    
    for (int i = 0; i < n; i++)
        maxChainLen[i] = 1;
    
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)
                maxChainLen[i] = maxChainLen[j] + 1;
    
    for (int i = 0; i < n; i++)
        if (max < maxChainLen[i])
            max = maxChainLen[i];
    
    delete[] maxChainLen;
    return max;
}

int main() {
    struct numPair arr[] = {{5, 24}, {15, 25}, {27, 40}, {50, 60}};
    int n = 4;
    cout << "Length of maximum size chain is " << maxChainLength(arr, n);
}

आउटपुट

Length of maximum size chain is 3