Ispiši lanac parova maksimalne duljine
Dano vam je n pari brojeva. U svakom paru prvi broj je uvijek manji od drugog broja. Par (c d) može slijediti drugi par (a b) ako b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs. Primjeri:
Input: (5 24) (39 60) (15 28) (27 40) (50 90) Output: (5 24) (27 40) (50 90) Input: (11 20) {10 40) (45 60) (39 40) Output: (11 20) (39 40) (45 60) U prethodni post o kojem smo raspravljali o problemu lanca parova maksimalne duljine. Međutim, post je pokrivao samo kod koji se odnosi na pronalaženje duljine lanca maksimalne veličine, ali ne i na konstrukciju lanca maksimalne veličine. U ovom ćemo postu raspravljati o tome kako konstruirati sam lanac parova maksimalne duljine. Ideja je prvo sortirati zadane parove prema rastućem redoslijedu njihovog prvog elementa. Neka arr[0..n-1] bude ulazni niz parova nakon sortiranja. Definiramo vektor L tako da je sam L[i] vektor koji pohranjuje lanac maksimalne duljine parova arr[0..i] koji završava s arr[i]. Stoga se za indeks i L[i] može rekurzivno napisati kao -
L[0] = {arr[0]} L[i] = {Max(L[j])} + arr[i] where j < i and arr[j].b < arr[i].a = arr[i] if there is no such j Na primjer za (5 24) (39 60) (15 28) (27 40) (50 90)
L[0]: (5 24) L[1]: (5 24) (39 60) L[2]: (15 28) L[3]: (5 24) (27 40) L[4]: (5 24) (27 40) (50 90)
Napominjemo da se parovi razvrstavaju jer moramo pronaći maksimalnu duljinu para, a poredak ovdje nije bitan. Ako ne sortiramo, dobit ćemo parove rastućim redoslijedom, ali to neće biti najveći mogući parovi. Ispod je implementacija gornje ideje –
C++ /* Dynamic Programming solution to construct Maximum Length Chain of Pairs */ #include using namespace std ; struct Pair { int a ; int b ; }; // comparator function for sort function int compare ( Pair x Pair y ) { return x . a < y . a ; } // Function to construct Maximum Length Chain // of Pairs void maxChainLength ( vector < Pair > arr ) { // Sort by start time sort ( arr . begin () arr . end () compare ); // L[i] stores maximum length of chain of // arr[0..i] that ends with arr[i]. vector < vector < Pair > > L ( arr . size ()); // L[0] is equal to arr[0] L [ 0 ]. push_back ( arr [ 0 ]); // start from index 1 for ( int i = 1 ; i < arr . size (); i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { // L[i] = {Max(L[j])} + arr[i] // where j < i and arr[j].b < arr[i].a if (( arr [ j ]. b < arr [ i ]. a ) && ( L [ j ]. size () > L [ i ]. size ())) L [ i ] = L [ j ]; } L [ i ]. push_back ( arr [ i ]); } // print max length vector vector < Pair > maxChain ; for ( vector < Pair > x : L ) if ( x . size () > maxChain . size ()) maxChain = x ; for ( Pair pair : maxChain ) cout < < '(' < < pair . a < < ' ' < < pair . b < < ') ' ; } // Driver Function int main () { Pair a [] = {{ 5 29 } { 39 40 } { 15 28 } { 27 40 } { 50 90 }}; int n = sizeof ( a ) / sizeof ( a [ 0 ]); vector < Pair > arr ( a a + n ); maxChainLength ( arr ); return 0 ; }
Java // Java program to implement the approach import java.util.ArrayList ; import java.util.Collections ; import java.util.List ; // User Defined Pair Class class Pair { int a ; int b ; } class GFG { // Custom comparison function public static int compare ( Pair x Pair y ) { return x . a - ( y . a ); } public static void maxChainLength ( List < Pair > arr ) { // Sort by start time Collections . sort ( arr Main :: compare ); // L[i] stores maximum length of chain of // arr[0..i] that ends with arr[i]. List < List < Pair >> L = new ArrayList <> (); // L[0] is equal to arr[0] List < Pair > l0 = new ArrayList <> (); l0 . add ( arr . get ( 0 )); L . add ( l0 ); for ( int i = 0 ; i < arr . size () - 1 ; i ++ ) { L . add ( new ArrayList <> ()); } // start from index 1 for ( int i = 1 ; i < arr . size (); i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { // L[i] = {Max(L[j])} + arr[i] // where j < i and arr[j].b < arr[i].a if ( arr . get ( j ). b < arr . get ( i ). a && L . get ( j ). size () > L . get ( i ). size ()) L . set ( i L . get ( j )); } L . get ( i ). add ( arr . get ( i )); } // print max length vector List < Pair > maxChain = new ArrayList <> (); for ( List < Pair > x : L ) if ( x . size () > maxChain . size ()) maxChain = x ; for ( Pair pair : maxChain ) System . out . println ( '(' + pair . a + ' ' + pair . b + ') ' ); } // Driver Code public static void main ( String [] args ) { Pair [] a = { new Pair () {{ a = 5 ; b = 29 ;}} new Pair () {{ a = 39 ; b = 40 ;}} new Pair () {{ a = 15 ; b = 28 ;}} new Pair () {{ a = 27 ; b = 40 ;}} new Pair () {{ a = 50 ; b = 90 ;}}}; int n = a . length ; List < Pair > arr = new ArrayList <> (); for ( Pair anA : a ) { arr . add ( anA ); } // Function call maxChainLength ( arr ); } } // This code is contributed by phasing17
Python3 # Dynamic Programming solution to construct # Maximum Length Chain of Pairs class Pair : def __init__ ( self a b ): self . a = a self . b = b def __lt__ ( self other ): return self . a < other . a def maxChainLength ( arr ): # Function to construct # Maximum Length Chain of Pairs # Sort by start time arr . sort () # L[i] stores maximum length of chain of # arr[0..i] that ends with arr[i]. L = [[] for x in range ( len ( arr ))] # L[0] is equal to arr[0] L [ 0 ] . append ( arr [ 0 ]) # start from index 1 for i in range ( 1 len ( arr )): # for every j less than i for j in range ( i ): # L[i] = {Max(L[j])} + arr[i] # where j < i and arr[j].b < arr[i].a if ( arr [ j ] . b < arr [ i ] . a and len ( L [ j ]) > len ( L [ i ])): L [ i ] = L [ j ] L [ i ] . append ( arr [ i ]) # print max length vector maxChain = [] for x in L : if len ( x ) > len ( maxChain ): maxChain = x for pair in maxChain : print ( '( {a} {b} )' . format ( a = pair . a b = pair . b ) end = ' ' ) print () # Driver Code if __name__ == '__main__' : arr = [ Pair ( 5 29 ) Pair ( 39 40 ) Pair ( 15 28 ) Pair ( 27 40 ) Pair ( 50 90 )] n = len ( arr ) maxChainLength ( arr ) # This code is contributed # by vibhu4agarwal
C# using System ; using System.Collections.Generic ; public class Pair { public int a ; public int b ; } public class Program { public static int Compare ( Pair x Pair y ) { return x . a - ( y . a ); } public static void MaxChainLength ( List < Pair > arr ) { // Sort by start time arr . Sort ( Compare ); // L[i] stores maximum length of chain of // arr[0..i] that ends with arr[i]. List < List < Pair >> L = new List < List < Pair >> (); // L[0] is equal to arr[0] L . Add ( new List < Pair > { arr [ 0 ] }); for ( int i = 0 ; i < arr . Count - 1 ; i ++ ) L . Add ( new List < Pair > ()); // start from index 1 for ( int i = 1 ; i < arr . Count ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { // L[i] = {Max(L[j])} + arr[i] // where j < i and arr[j].b < arr[i].a if ( arr [ j ]. b < arr [ i ]. a && L [ j ]. Count > L [ i ]. Count ) L [ i ] = L [ j ]; } L [ i ]. Add ( arr [ i ]); } // print max length vector List < Pair > maxChain = new List < Pair > (); foreach ( List < Pair > x in L ) if ( x . Count > maxChain . Count ) maxChain = x ; foreach ( Pair pair in maxChain ) Console . WriteLine ( '(' + pair . a + ' ' + pair . b + ') ' ); } public static void Main () { Pair [] a = { new Pair () { a = 5 b = 29 } new Pair () { a = 39 b = 40 } new Pair () { a = 15 b = 28 } new Pair () { a = 27 b = 40 } new Pair () { a = 50 b = 90 } }; int n = a . Length ; List < Pair > arr = new List < Pair > ( a ); MaxChainLength ( arr ); } }
JavaScript < script > // Dynamic Programming solution to construct // Maximum Length Chain of Pairs class Pair { constructor ( a b ){ this . a = a this . b = b } } function maxChainLength ( arr ){ // Function to construct // Maximum Length Chain of Pairs // Sort by start time arr . sort (( c d ) => c . a - d . a ) // L[i] stores maximum length of chain of // arr[0..i] that ends with arr[i]. let L = new Array ( arr . length ). fill ( 0 ). map (()=> new Array ()) // L[0] is equal to arr[0] L [ 0 ]. push ( arr [ 0 ]) // start from index 1 for ( let i = 1 ; i < arr . length ; i ++ ){ // for every j less than i for ( let j = 0 ; j < i ; j ++ ){ // L[i] = {Max(L[j])} + arr[i] // where j < i and arr[j].b < arr[i].a if ( arr [ j ]. b < arr [ i ]. a && L [ j ]. length > L [ i ]. length ) L [ i ] = L [ j ] } L [ i ]. push ( arr [ i ]) } // print max length vector let maxChain = [] for ( let x of L ){ if ( x . length > maxChain . length ) maxChain = x } for ( let pair of maxChain ) document . write ( `( ${ pair . a } ${ pair . b } ) ` ) document . write ( ' ' ) } // driver code let arr = [ new Pair ( 5 29 ) new Pair ( 39 40 ) new Pair ( 15 28 ) new Pair ( 27 40 ) new Pair ( 50 90 )] let n = arr . length maxChainLength ( arr ) /// This code is contributed by shinjanpatra < /script>
Izlaz:
(5 29) (39 40) (50 90)
Vremenska složenost gornje rješenje dinamičkog programiranja je O(n 2 ) gdje je n broj parova. Pomoćni prostor koristi program je O(n 2 ).
