ജോഡികളുടെ പരമാവധി ദൈർഘ്യ ശൃംഖല അച്ചടിക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

“ജോഡികളുടെ പരമാവധി ദൈർഘ്യ ശൃംഖല അച്ചടിക്കുക” എന്ന പ്രശ്‌നം നിങ്ങൾക്ക് ചില ജോഡി നമ്പറുകൾ നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഓരോ ജോഡിയിലും ആദ്യത്തെ സംഖ്യ രണ്ടാമത്തെ സംഖ്യയേക്കാൾ ചെറുതാണെന്ന് നൽകിയിരിക്കുന്നു. മുമ്പത്തെ ജോഡിയുടെ (എ, ബി) രണ്ടാമത്തെ സംഖ്യ ജോഡിക്ക് ശേഷമുള്ള (സി, ഡി) (ബി <സി) ശേഷമുള്ള ആദ്യ സംഖ്യയേക്കാൾ ചെറുതായ ഏറ്റവും ദൈർഘ്യമേറിയ ചെയിൻ ഇപ്പോൾ നിങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N ^ 2), കാരണം പ്രശ്നം എൽ‌ഐ‌എസ് പ്രശ്‌നത്തിന് സമാനമാണ്. നിലവിലെ ജോഡി ചേർത്താൽ ഒരു ചെയിൻ ജോഡി കണ്ടെത്താൻ ഈ പ്രശ്‌നത്തിലും ഞങ്ങൾ ഒരു നെസ്റ്റഡ് ലൂപ്പ് ഉപയോഗിച്ചു. അവസ്ഥ തൃപ്തികരമായി തുടരുന്നു. അങ്ങനെ സമയ സങ്കീർണ്ണത പോളിനോമിയലാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N ^ 2), ഞങ്ങൾ വെക്റ്ററുകളുടെ വെക്റ്റർ ഉപയോഗിച്ചതിനാൽ സ്പേസ് സങ്കീർണ്ണതയും പോളിനോമിയലാണ്. ഏറ്റവും മോശം അവസ്ഥയിൽ പരമാവധി ചെയിൻ ദൈർഘ്യം ഇൻപുട്ടിന്റെ വലുപ്പത്തിന് തുല്യമാകുമ്പോൾ. അപ്പോൾ നമ്മുടെ വെക്റ്ററുകളുടെ വെക്റ്ററിന് O (N ^ 2) ജോഡികൾ ഉണ്ടാകും. അതിനാൽ ആവശ്യമായ സ്ഥലവും പോളിനോമിയലാണ്.