जोडीहरूको अधिकतम लम्बाइ श्रृंखला प्रिन्ट गर्नुहोस्


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन
डायनामिक प्रोग्रामिंग

समस्या वक्तव्य

समस्या "जोडीहरूको अधिकतम लम्बाई श्रृंखला प्रिन्ट गर्नुहोस्" भन्छ कि तपाईंलाई केही जोडी संख्या दिइन्छ। यो दिइएको छ कि प्रत्येक जोडीमा, पहिलो नम्बर दोस्रो नम्बर भन्दा सानो छ। अब तपाईंले सब भन्दा लामो श्रृंखला फेला पार्न आवश्यक छ कि अघिल्लो जोडीको दोस्रो संख्या (a, b) अर्को जोडी (c, d) पछिल्लो नम्बर भन्दा सानो छ जुन (b <c) छ।

उदाहरणका

(1, 10), (11, 25), (26, 35), (36, 50)
(1, 10), (11, 25), (26, 35), (36, 50)

स्पष्टीकरण

हामीले सबै जोडीहरू चयन गर्‍यौं किनभने सबै जोडीहरूले सर्त सन्तुष्ट गरे।

(1, 2), (10, 30), (5, 6), (15, 25), (17, 21)
(1, 2), (5, 6), (10, 30)

स्पष्टीकरण

हामीले चयन गरेको तेस्रो जोडीले केही फरक पार्दैन। हामीले बाँकी रहेका तीन जोडी मध्ये कुनै पनि छनौट गर्न सक्दछौं किनकि तिनीहरू सबै सर्तमा सन्तुष्ट छन्। तर हामी तीन मध्ये तीन मध्ये कुनै पनि दुई छनौट गर्न सक्दैनौं।

जोडीहरूको अधिकतम लम्बाइ चेन प्रिन्ट गर्न दृष्टिकोण

समस्याले हामीलाई जोडीहरूको अधिकतम लम्बाइ श्रृंखला फेला पार्न र प्रिन्ट गर्न सोध्छ। त्यसो भए यहाँ अधिकतम लम्बाई भनेको के हो? यहाँ अधिकतम लम्बाई परिणाममा जोडी संख्या प्रतिनिधित्व गर्दछ। त्यसो भए अन्तमा हामीले ती जोडीहरू पत्ता लगाउनु पर्छ जुन अधिकतम लम्बाई हो।

हामीले छलफल गरिसकेका छौं यो समस्या। हामीले छलफल गरेको समस्याले हामीलाई अधिकतम लम्बाइ पत्ता लगाउन भन्यो। त्यहाँ हामीले समस्या समाधान गर्न विभिन्न दृष्टिकोणहरुमा छलफल गर्‍यौं। यहाँ समस्याको यस अंशमा हामीले पनि यस्ता जोडीहरू खोज्नु पर्छ। डायनामिक प्रोग्रामिंगको प्रयोग गरेर हामी समस्या समाधान गर्ने छौं किनभने पुनरावर्तन प्रयोग गर्दा यसलाई हल गर्ने समय सीमा भन्दा बढी हुनेछ। पुनरावृत्ति सम्बन्ध धेरै LIS को समान छ (अब बढ्ने उपसक्व)। हामी भेक्टरको भेक्टर बनाउनेछौं। भेक्टरहरूको यस भेक्टरको प्रत्येक तत्वले जोडहरूलाई जनाउँछ जसले अधिकतम लम्बाइ अनुक्रम बनाउँदछ जब हामी इनपुटमा हालको तत्त्वसँग सम्बन्धित तत्व छनौट गर्दछौं।

त्यसोभए, पुनरावृत्ति सम्बन्ध हो

जोडीहरूको अधिकतम लम्बाइ श्रृंखला प्रिन्ट गर्नुहोस्

कोड

C ++ कोड जोडाहरूमा अधिकतम लम्बाइ चेन प्रिन्ट गर्न

#include <bits/stdc++.h>
using namespace std;


void maxChainLength(vector<pair<int,int>> &input) 
{ 
    sort(input.begin(), input.end());
  
    int n = input.size();
    vector<vector<pair<int,int>>> dp(n); 
  	int mx = 0;
    // base case
    dp[0].push_back(input[0]); 
    for(int i=1;i<n;i++) 
    {
        for(int j=0;j<i;j++)
        {
            if ((input[j].second < input[i].first) && (dp[j].size() > dp[i].size())) // the condition must be satisfied 
                dp[i] = dp[j];
        } 
        dp[i].push_back(input[i]);
        if(dp[i].size() > dp[mx].size())
        	mx = i;
    }
    for(auto x: dp[mx])
    	cout<<"("<<x.first<<", "<<x.second<<") ";
} 

int main()
{ 
    vector<pair<int,int>> input = {{1, 2}, {10, 30}, {5, 6}, {15, 25}, {17, 21}};
    maxChainLength(input);
}
(1, 2) (5, 6) (10, 30)

जाभा कोड जोडीहरूको अधिकतम लम्बाइ चेन प्रिन्ट गर्न

import java.util.*;

class Main{
    static void maxChainLength(ArrayList<ArrayList<Integer>> input)
    {
        Collections.sort(input, new Comparator<ArrayList<Integer>> () {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                return a.get(0).compareTo(b.get(0));
            }
        });

        int n = input.size();
        ArrayList<ArrayList<ArrayList<Integer>>> dp = new ArrayList<ArrayList<ArrayList<Integer>>>();
        for(int i=0;i<n;i++)
            dp.add(new ArrayList<ArrayList<Integer>>());
        int mx = 0;
        // base case
        dp.get(0).add(input.get(0));
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(input.get(j).get(1) < input.get(i).get(0) && (dp.get(j).size() > dp.get(i).size())){
                    dp.set(i, new ArrayList<ArrayList<Integer>>(dp.get(j)));
                }
            }
            dp.get(i).add(input.get(i));
            if(dp.get(i).size() > dp.get(mx).size())
                mx = i;
        }
        for(ArrayList<Integer> x: dp.get(mx))
            System.out.print("("+x.get(0)+", "+x.get(1)+") ");
    }

    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> input = new ArrayList<ArrayList<Integer>>();
        input.add(new ArrayList(Arrays.asList(1, 2)));
        input.add(new ArrayList(Arrays.asList(10, 30)));
        input.add(new ArrayList(Arrays.asList(5, 6)));
        input.add(new ArrayList(Arrays.asList(15, 25)));
        input.add(new ArrayList(Arrays.asList(17, 21)));
        maxChainLength(input);
    }
}
(1, 2) (5, 6) (10, 30)

जटिलता विश्लेषण

समय जटिलता

O (N ^ 2), किनभने समस्या LIS समस्या जस्तै छ। र यो समस्यामा हामीले नेस्टेड लूप प्रयोग गरेका छौं एक चेन जोडी खोज्नको लागि यदि हामी हालको जोडी थप्छौं भने। अवस्था सन्तुष्ट छ। यसैले समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (N ^ 2), स्पेस जटिलता पनि बहुपद हो किनभने हामीले भेक्टरको भेक्टर प्रयोग गरेका छौं। सबैभन्दा खराब अवस्थामा जब अधिकतम चेनको लम्बाई इनपुटको आकार बराबर हुन्छ। त्यसोभए हाम्रो भेक्टरको ओ ओ हुनेछ (एन ^ २) जोडीहरू। त्यसकारण आवाश्यक ठाउँ पनि बहुपद हो।