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


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना
गतिशील प्रोग्रामिंग

समस्या का विवरण

समस्या "प्रिंट्स की अधिकतम लंबाई श्रृंखला" बताती है कि आपको कुछ जोड़े संख्याएँ दी गई हैं। यह दिया जाता है कि प्रत्येक जोड़ी में, पहली संख्या दूसरी संख्या से छोटी है। अब आपको सबसे लंबी श्रृंखला खोजने की आवश्यकता है जैसे कि पूर्ववर्ती जोड़ी (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)

व्याख्या

तीसरी जोड़ी जिसे हमने चुना है, इससे कोई फर्क नहीं पड़ता। हम शेष तीन जोड़ियों में से किसी एक का चयन कर सकते थे क्योंकि वे सभी शर्त को पूरा करते थे। लेकिन हम तीन में से किसी भी दो को नहीं चुन सकते हैं।

जोड़े की अधिकतम लंबाई श्रृंखला मुद्रित करने के लिए दृष्टिकोण

समस्या हमें जोड़े की अधिकतम लंबाई श्रृंखला को खोजने और प्रिंट करने के लिए कहती है। तो यहां अधिकतम लंबाई का क्या मतलब है? यहां अधिकतम लंबाई परिणाम में जोड़े की संख्या का प्रतिनिधित्व करती है। इसलिए अंत में, हमें उन जोड़ों को खोजने की जरूरत है जो अधिकतम लंबाई का गठन करते हैं।

हम पहले ही चर्चा कर चुके हैं इस समस्या। जिस समस्या पर हमने चर्चा की, उसने हमें अधिकतम लंबाई खोजने के लिए कहा। वहां हमने समस्या से निपटने के लिए विभिन्न तरीकों पर चर्चा की। यहाँ समस्या के इस भाग में, हमें ऐसे जोड़े खोजने की भी आवश्यकता है। हम डायनेमिक प्रोग्रामिंग का उपयोग करके समस्या का समाधान करेंगे क्योंकि इसे पुनरावृत्ति का उपयोग करके हल करना समय सीमा से अधिक होगा। पुनरावृत्ति का संबंध एलआईएस (सबसे लंबे समय तक बढ़ती उपसर्ग) के समान है। हम वैक्टर का एक वेक्टर बनाएंगे। वैक्टर के इस वेक्टर का प्रत्येक तत्व उन जोड़ों को निरूपित करेगा जो अधिकतम लंबाई अनुक्रम बनाते हैं जब हम हमेशा इनपुट में वर्तमान तत्व के अनुरूप तत्व चुनते हैं।

तो, पुनरावृत्ति संबंध है

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

कोड

सी ++ कोड जोड़े की अधिकतम लंबाई श्रृंखला मुद्रित करने के लिए

#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)

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

समय जटिलता

ओ (एन ^ 2), क्योंकि समस्या LIS समस्या के समान है। और इस समस्या में भी हमने एक चेन जोड़ी को खोजने के लिए नेस्टेड लूप का उपयोग किया है, जैसे कि अगर हम वर्तमान जोड़ी को जोड़ते हैं। हालत संतुष्ट बनी हुई है। इस प्रकार समय जटिलता बहुपद है।

अंतरिक्ष जटिलता

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