/* 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 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>