जोड़े की अधिकतम लंबाई श्रृंखला

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

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

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

Input:
A chain of number pairs. {(5, 24), (15, 25), (27, 40), (50, 60)}
Output:
Largest length of the chain as given criteria. Here the length is 3.

एल्गोरिदम

maxChainLength(arr, n)

श्रृंखला के प्रत्येक तत्व में दो तत्व होंगे a और b

इनपुट - जोड़े की सरणी, सरणी में मदों की संख्या।

आउटपुट - अधिकतम लंबाई।

Begin
   define maxChainLen array of size n, and fill with 1
   max := 0

   for i := 1 to n, do
      for j := 0 to i-1, do
         if arr[i].a > arr[j].b and maxChainLen[i] < maxChainLen[j] + 1
            maxChainLen[i] := maxChainLen[j] + 1
      done
   done

   max := maximum length in maxChainLen array
   return max
End

उदाहरण

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

struct numPair {    //define pair as structure
   int a;
   int b;
};

int maxChainLength(numPair arr[], int n) {
   int max = 0;
   int *maxChainLen = new int[n];    //create array of size n

   for (int i = 0; i < n; i++ )    //Initialize Max Chain length values for all indexes
      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;

   // maxChainLen[i] now holds the max chain length ending with pair i

   for (int i = 0; i < n; i++ )
      if ( max < maxChainLen[i] )
         max = maxChainLen[i];    //find maximum among all chain length values
   delete[] maxChainLen;    //deallocate memory
   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