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