Te dan n pares de números. En cada par, el primer número siempre es menor que el segundo. Un par (c d) puede seguir a otro par (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. Ejemplos:
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) En anterior publicación que hemos discutido sobre el problema de la cadena de pares de longitud máxima. Sin embargo, la publicación solo cubría el código relacionado con encontrar la longitud de la cadena de tamaño máximo, pero no con la construcción de la cadena de tamaño máximo. En esta publicación discutiremos cómo construir la propia cadena de pares de longitud máxima. La idea es ordenar primero los pares dados en orden creciente de su primer elemento. Sea arr[0..n-1] la matriz de entrada de pares después de la clasificación. Definimos el vector L tal que L[i] es en sí mismo un vector que almacena una cadena de longitud máxima de pares de arr[0..i] que termina con arr[i]. Por lo tanto, para un índice i, L[i] se puede escribir de forma recursiva como:
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 Por ejemplo para (5 24) (39 60) (15 28) (27 40) (50 90)
100kmh a mph
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)
Tenga en cuenta que la clasificación de pares se realiza porque necesitamos encontrar la longitud máxima del par y el orden no importa aquí. Si no ordenamos obtendremos pares en orden creciente pero no serán los pares máximos posibles. A continuación se muestra la implementación de la idea anterior:
C++/* Dynamic Programming solution to construct Maximum Length Chain of Pairs */ #include
// 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
# 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
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); } }
<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((cd) => 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>
Producción:
(5 29) (39 40) (50 90)
Complejidad del tiempo de la solución de programación dinámica anterior es O (n2) donde n es el número de pares. Espacio auxiliar utilizado por el programa es O(n2).