જોડીની મહત્તમ લંબાઈ ચેઇન છાપો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન
ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા નિવેદન

સમસ્યા "પ્રિન્ટ્સ મેક્સિમમ લંબાઈ ચેઇન ઓફ જોડ્સ" કહે છે કે તમને સંખ્યાની જોડી આપવામાં આવે છે. તે આપવામાં આવે છે કે દરેક જોડીમાં, પ્રથમ નંબર બીજા નંબર કરતા નાનો હોય છે. હવે તમારે સૌથી લાંબી સાંકળ શોધવાની જરૂર છે કે પહેલાની જોડીની બીજી નંબર (એ, બી) જોડી પછીની પ્રથમ સંખ્યા (સી, ડી) કે (બી <સી) કરતા ઓછી છે.

ઉદાહરણ

(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), કારણ કે સમસ્યા એલ.આઈ.એસ. સમસ્યા જેવી જ છે. અને આ સમસ્યામાં પણ અમે ચેન જોડી શોધવા માટે નેસ્ડ લૂપનો ઉપયોગ કર્યો છે જેમ કે જો આપણે વર્તમાન જોડી ઉમેરીશું. સ્થિતિ સંતુષ્ટ રહે છે. આમ સમય જટિલતા બહુપદી છે.

અવકાશ જટિલતા

ઓ (એન ^ 2), સ્પેસ જટિલતા પણ બહુપદી છે કારણ કે આપણે વેક્ટરના વેક્ટરનો ઉપયોગ કર્યો છે. સૌથી ખરાબ કિસ્સામાં જ્યારે મહત્તમ સાંકળની લંબાઈ ઇનપુટના કદની બરાબર હોય. પછી અમારા વેક્ટરના વેક્ટરમાં ઓ (એન ^ 2) જોડીઓ હશે. આમ જરૂરી જગ્યા પણ બહુપદી છે.