Du får n par med tal. I varje par är det första talet alltid mindre än det andra talet. Ett par (c d) kan följa efter ett annat par (a b) om 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. Exempel:
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) I tidigare inlägg som vi har diskuterat om problemet med maximal längdkedja av par. Men inlägget omfattade endast koden för att hitta längden på kedjan med maximal storlek men inte till konstruktionen av kedjan med maximal storlek. I det här inlägget kommer vi att diskutera hur man konstruerar själva kedjan med maximal längd av par. Tanken är att först sortera givna par i ökande ordning efter deras första element. Låt arr[0..n-1] vara inmatningsmatrisen av par efter sortering. Vi definierar vektor L så att L[i] i sig själv är en vektor som lagrar maximal längdkedja av par av arr[0..i] som slutar med arr[i]. Därför för ett index kan i L[i] skrivas rekursivt som -
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 Till exempel för (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)
Observera att sortering av par görs eftersom vi behöver hitta den maximala parlängden och beställning spelar ingen roll här. Om vi inte sorterar kommer vi att få par i ökande ordning men de kommer inte att vara maximalt möjliga par. Nedan är implementeringen av ovanstående idé -
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>
Produktion:
(5 29) (39 40) (50 90)
Tidskomplexitet av ovanstående dynamisk programmeringslösning är O(n2) där n är antalet par. Hjälputrymme som används av programmet är O(n2).