Imprimer une chaîne de paires de longueur maximale
On vous donne n paires de nombres. Dans chaque paire, le premier nombre est toujours plus petit que le deuxième nombre. Une paire (c d) peut suivre une autre paire (a b) si 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. Exemples :
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) Dans précédent post dont nous avons discuté sur le problème de la chaîne de longueur maximale de paires. Cependant, le message ne couvrait que le code lié à la recherche de la longueur de la chaîne de taille maximale, mais pas à la construction de la chaîne de taille maximale. Dans cet article, nous verrons comment construire elle-même une chaîne de paires de longueur maximale. L’idée est de trier d’abord les paires données par ordre croissant de leur premier élément. Soit arr[0..n-1] le tableau d'entrée de paires après le tri. Nous définissons le vecteur L tel que L[i] est lui-même un vecteur qui stocke une chaîne de longueur maximale de paires de arr[0..i] qui se termine par arr[i]. Par conséquent, pour un index i L[i] peut être écrit récursivement sous la forme -
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 Par exemple pour (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)
Veuillez noter que le tri des paires est effectué car nous devons trouver la longueur maximale des paires et que l'ordre n'a pas d'importance ici. Si nous ne trions pas, nous obtiendrons des paires par ordre croissant, mais ce ne sera pas le maximum de paires possibles. Vous trouverez ci-dessous la mise en œuvre de l’idée ci-dessus –
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>
Sortir:
(5 29) (39 40) (50 90)
Complexité temporelle de la solution de programmation dynamique ci-dessus est O (n 2 ) où n est le nombre de paires. Espace auxiliaire utilisé par le programme est O(n 2 ).
