Je krijgt n getallenparen. In elk paar is het eerste getal altijd kleiner dan het tweede getal. Een paar (c d) kan een ander paar (a b) volgen als 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. Voorbeelden:
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) In vorig post die we hebben besproken over het probleem van de maximale lengteketen van paren. Het bericht behandelde echter alleen code met betrekking tot het vinden van de lengte van een ketting met maximale grootte, maar niet met de constructie van een ketting met maximale grootte. In dit bericht zullen we bespreken hoe je de maximale lengteketen van paren zelf kunt construeren. Het idee is om gegeven paren eerst te sorteren in oplopende volgorde van hun eerste element. Laat arr[0..n-1] de invoerarray van paren zijn na het sorteren. We definiëren vector L zo dat L[i] zelf een vector is die de maximale lengteketen van paren van arr[0..i] opslaat die eindigt op arr[i]. Daarom kan L[i] voor een index i L[i] recursief worden geschreven als -
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 Bijvoorbeeld voor (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)
Let op: het sorteren van paren gebeurt omdat we de maximale paarlengte moeten vinden en bestellen doet er hier niet toe. Als we niet sorteren, krijgen we paren in oplopende volgorde, maar het zijn niet de maximaal mogelijke paren. Hieronder vindt u de implementatie van het bovenstaande idee -
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>
Uitgang:
(5 29) (39 40) (50 90)
Tijdcomplexiteit van bovenstaande dynamische programmeeroplossing is O (n2) waarbij n het aantal paren is. Hulpruimte gebruikt door het programma is O(n2).