పెయిర్స్ యొక్క గరిష్ట పొడవు గొలుసును ముద్రించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్
డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

“పెయిర్స్ యొక్క గరిష్ట పొడవు గొలుసును ముద్రించండి” సమస్య మీకు కొన్ని జతల సంఖ్యలను ఇస్తుందని పేర్కొంది. ప్రతి జతలో, మొదటి సంఖ్య రెండవ సంఖ్య కంటే తక్కువగా ఉంటుందని ఇవ్వబడింది. ఇప్పుడు మీరు పొడవైన గొలుసును కనుగొనవలసి ఉంది, అంటే మునుపటి జత యొక్క రెండవ సంఖ్య (ఎ, బి) తరువాత జత (సి, డి) తరువాత మొదటి సంఖ్య (బి <సి) కంటే చిన్నది.

ఉదాహరణ

(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 (లాంగ్టెస్ట్ పెరుగుతున్న తరువాతి) తో చాలా పోలి ఉంటుంది. మేము వెక్టర్స్ యొక్క వెక్టర్ను సృష్టిస్తాము. వెక్టర్స్ యొక్క ఈ వెక్టార్ యొక్క ప్రతి మూలకం మేము ఎల్లప్పుడూ ఇన్పుట్లోని ప్రస్తుత మూలకానికి అనుగుణమైన మూలకాన్ని ఎన్నుకున్నప్పుడు గరిష్ట పొడవు క్రమాన్ని చేసే జతలను సూచిస్తుంది.

కాబట్టి, పునరావృత సంబంధం

పెయిర్స్ యొక్క గరిష్ట పొడవు గొలుసును ముద్రించండి

కోడ్

పెయిర్స్ యొక్క గరిష్ట పొడవు గొలుసును ముద్రించడానికి సి ++ కోడ్

#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), స్థల సంక్లిష్టత కూడా బహుపది, ఎందుకంటే మేము వెక్టర్స్ వెక్టర్‌ను ఉపయోగించాము. చెత్త సందర్భంలో గరిష్ట గొలుసు పొడవు ఇన్పుట్ పరిమాణానికి సమానంగా ఉన్నప్పుడు. అప్పుడు మన వెక్టార్ యొక్క వెక్టర్ O (N ^ 2) జతలను కలిగి ఉంటుంది. అందువల్ల అవసరమైన స్థలం కూడా బహుపది.