C++-এ পেয়ার গুলোর ম্যাক্সিমাম দৈর্ঘ্যের চেইন বের করা

একটি পেয়ার চেইন দেওয়া আছে। প্রতিটি পেয়ার-এ দুটি ইন্টিজার থাকে এবং প্রথম ইন্টিজারটি সবসময় ছোট, দ্বিতীয়টি বড়। চেইন নির্মাণের জন্যও একই নিয়ম প্রয়োগ করা যায়। একটি পেয়ার (x, y) কে একটি পেয়ার (p, q)-এর পরে যোগ করা যাবে, শুধু যদি q < x হয়।

এই সমস্যা সমাধানের জন্য, প্রথমে দিয়ে गये পেয়ার গুলোকে প্রথম এলিমেন্ট অনুযায়ী ক্রমবর্ধমান ক interrumpে সোর্ট করতে হবে। এরপর আমরা একটি পেয়ার-এর দ্বিতীয় এলিমেন্টকে পরবর্তী পেয়ার-এর প্রথম এলিমেন্টের সাথে তুলনা করব।

ইনপুট

একটি সংখ্যা পেয়ার চেইন। {(5, 24), (15, 25), (27, 40), (50, 60)}

আউটপুট

দেওয়া শর্ত অনুযায়ী চেইন-এর সর্বোচ্চ দৈর্ঘ্য। এখানে দৈর্ঘ্য ৩।

অ্যালগরিদম

maxChainLength(arr, n) প্রতিটি চেইন এলিমেন্টে দুটি এলিমেন্ট a এবং b থাকবে
ইনপুট: পেয়ার গুলোর অ্যারে, অ্যারে-এ আইটেম সংখ্যা।
আউটপুট: সর্বোচ্চ দৈর্ঘ্য।
শুরু
    maxChainLen অ্যারে ডিফাইন করো সাইজ n, এবং ১ দিয়ে ফিল করো
    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]; // সাইজ 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;
    // maxChainLen[i] এখন পেয়ার i দিয়ে শেষ হয় এমন ম্যাক্স চেইন দৈর্ঘ্য ধারণ করছে
    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