// C++ program for weighted job scheduling using Dynamic   // Programming and Binary Search   #include          using     namespace     std  ;   // A job has start time finish time and profit.   struct     Job   {      int     start       finish       profit  ;   };   // to store subset of jobs   struct     weightedJob   {      // vector of Jobs      vector   <  Job  >     job  ;      // find profit associated with included Jobs      int     value  ;   };   // A utility function that is used for sorting events   // according to finish time   bool     jobComparator  (  Job     s1       Job     s2  )   {      return     (  s1  .  finish      <     s2  .  finish  );   }   // A Binary Search based function to find the latest job   // (before current job) that doesn't conflict with current   // job. 'index' is index of the current job. This function   // returns -1 if all jobs before index conflict with it. The   // array jobs[] is sorted in increasing order of finish time   int     latestNonConflict  (  Job     jobs  []     int     index  )   {      // Initialize 'lo' and 'hi' for Binary Search      int     lo     =     0       hi     =     index     -     1  ;      // Perform binary Search iteratively      while     (  lo      <=     hi  )      {      int     mid     =     (  lo     +     hi  )     /     2  ;      if     (  jobs  [  mid  ].  finish      <=     jobs  [  index  ].  start  )      {      if     (  jobs  [  mid     +     1  ].  finish      <=     jobs  [  index  ].  start  )      lo     =     mid     +     1  ;      else      return     mid  ;      }      else      hi     =     mid     -     1  ;      }      return     -1  ;   }   // The main function that finds the subset of jobs   // associated with maximum profit such that no two   // jobs in the subset overlap.   int     findMaxProfit  (  Job     arr  []     int     n  )   {      // Sort jobs according to finish time      sort  (  arr       arr     +     n       jobComparator  );      // Create an array to store solutions of subproblems.      // DP[i] stores the Jobs involved and their total profit      // till arr[i] (including arr[i])      weightedJob     DP  [  n  ];      // initialize DP[0] to arr[0]      DP  [  0  ].  value     =     arr  [  0  ].  profit  ;      DP  [  0  ].  job  .  push_back  (  arr  [  0  ]);      // Fill entries in DP[] using recursive property      for     (  int     i     =     1  ;     i      <     n  ;     i  ++  )      {      // Find profit including the current job      int     inclProf     =     arr  [  i  ].  profit  ;      int     l     =     latestNonConflict  (  arr       i  );      if     (  l     !=     -     1  )      inclProf     +=     DP  [  l  ].  value  ;      // Store maximum of including and excluding      if     (  inclProf     >     DP  [  i     -     1  ].  value  )      {      DP  [  i  ].  value     =     inclProf  ;      // including previous jobs and current job      DP  [  i  ].  job     =     DP  [  l  ].  job  ;      DP  [  i  ].  job  .  push_back  (  arr  [  i  ]);      }      else      // excluding the current job      DP  [  i  ]     =     DP  [  i     -     1  ];      }      // DP[n - 1] stores the result      cout      < <     'Optimal Jobs for maximum profits are  n  '     ;      for     (  int     i  =  0  ;     i   <  DP  [  n  -1  ].  job  .  size  ();     i  ++  )      {      Job     j     =     DP  [  n  -1  ].  job  [  i  ];      cout      < <     '('      < <     j  .  start      < <     ' '      < <     j  .  finish       < <     ' '      < <     j  .  profit      < <     ')'      < <     endl  ;      }      cout      < <     '  n  Total Optimal profit is '      < <     DP  [  n     -     1  ].  value  ;   }   // Driver program   int     main  ()   {      Job     arr  []     =     {{  3       5       20  }     {  1       2       50  }     {  6       19       100  }      {  2       100       200  }     };      int     n     =     sizeof  (  arr  )  /  sizeof  (  arr  [  0  ]);      findMaxProfit  (  arr       n  );      return     0  ;   }   

   // Java program for weighted job scheduling using Dynamic   // Programming and Binary Search   import     java.util.*  ;   public     class   WeightedJobScheduling     {   // A job has start time finish time and profit.   static     class   Job     {      int     start       finish       profit  ;      public     Job  (  int     start       int     finish       int     profit  )     {      this  .  start     =     start  ;      this  .  finish     =     finish  ;      this  .  profit     =     profit  ;      }   }   // to store subset of jobs   static     class   weightedJob     {      // vector of Jobs      List   <  Job  >     job  ;      // find profit associated with included Jobs      int     value  ;      public     weightedJob  ()     {      job     =     new     ArrayList   <>  ();      }   }   // A utility function that is used for sorting events   // according to finish time   static     class   JobComparator     implements     Comparator   <  Job  >     {      @Override      public     int     compare  (  Job     j1       Job     j2  )     {      return     j1  .  finish     -     j2  .  finish  ;      }   }   // A Binary Search based function to find the latest job   // (before current job) that doesn't conflict with current   // job. 'index' is index of the current job. This function   // returns -1 if all jobs before index conflict with it. The   // array jobs[] is sorted in increasing order of finish time   static     int     latestNonConflict  (  Job  []     jobs       int     index  )     {      // Initialize 'lo' and 'hi' for Binary Search      int     lo     =     0       hi     =     index     -     1  ;      // Perform binary Search iteratively      while     (  lo      <=     hi  )     {      int     mid     =     (  lo     +     hi  )     /     2  ;      if     (  jobs  [  mid  ]  .  finish      <=     jobs  [  index  ]  .  start  )     {      if     (  jobs  [  mid     +     1  ]  .  finish      <=     jobs  [  index  ]  .  start  )     {      lo     =     mid     +     1  ;      }     else     {      return     mid  ;      }      }     else     {      hi     =     mid     -     1  ;      }      }      return     -  1  ;   }   // The main function that finds the subset of jobs   // associated with maximum profit such that no two   // jobs in the subset overlap.   static     int     findMaxProfit  (  Job  []     arr  )     {      // Sort jobs according to finish time      Arrays  .  sort  (  arr       new     JobComparator  ());   // Create an array to store solutions of subproblems.      // DP[i] stores the Jobs involved and their total profit      // till arr[i] (including arr[i])      weightedJob  []     DP     =     new     weightedJob  [  arr  .  length  ]  ;      DP  [  0  ]     =     new     weightedJob  ();      // initialize DP[0] to arr[0]      DP  [  0  ]  .  value     =     arr  [  0  ]  .  profit  ;      DP  [  0  ]  .  job  .  add  (  arr  [  0  ]  );      // Fill entries in DP[] using recursive property      for     (  int     i     =     1  ;     i      <     arr  .  length  ;     i  ++  )     {      // Find profit including the current job      int     inclProf     =     arr  [  i  ]  .  profit  ;      int     l     =     latestNonConflict  (  arr       i  );      if     (  l     !=     -  1  )     {      inclProf     +=     DP  [  l  ]  .  value  ;      }      // Store maximum of including and excluding      if     (  inclProf     >     DP  [  i     -     1  ]  .  value  )     {      DP  [  i  ]     =     new     weightedJob  ();      DP  [  i  ]  .  value     =     inclProf  ;      DP  [  i  ]  .  job  .  addAll  (  DP  [  l  ]  .  job  );      DP  [  i  ]  .  job  .  add  (  arr  [  i  ]  );      }     else     {          DP  [  i  ]     =     DP  [  i     -     1  ]  ;      }      }      // DP[n - 1] stores the result      System  .  out  .  println  (  'Optimal Jobs for maximum profits are'  );      for     (  Job     j     :     DP  [  arr  .  length     -     1  ]  .  job  )     {      System  .  out  .  println  (  '('     +     j  .  start     +     ' '     +     j  .  finish     +     ' '     +     j  .  profit     +     ')'  );      }      System  .  out  .  println  (  'nTotal Optimal profit is '     +     DP  [  arr  .  length     -     1  ]  .  value  );      return     DP  [  arr  .  length     -     1  ]  .  value  ;   }       // Driver program   public     static     void     main  (  String  []     args  )     {      Job  []     arr     =     {     new     Job  (  3       5       20  )         new     Job  (  1       2       50  )      new     Job  (  6       19       100  )         new     Job  (  2       100       200  )     };      findMaxProfit  (  arr  );   }   }   // This code is contributed by ratiagrawal.   

   from   typing   import   List     Tuple   def   find_max_profit  (  jobs  :   List  [  Tuple  [  int     int     int  ]])   ->   int  :   n   =   len  (  jobs  )   # Sort the jobs in ascending order of their finish times   jobs  .  sort  (  key  =  lambda   x  :   x  [  1  ])   # Initialize DP array with the first job and its profit as the maximum profit   DP   =   [{  'value'  :   jobs  [  0  ][  2  ]   'jobs'  :   [  jobs  [  0  ]]}]   # Iterate over the remaining jobs   for   i   in   range  (  1     n  ):   # Find the index of the latest non-conflicting job   l   =   latest_non_conflict  (  jobs     i  )   # Calculate the profit that can be obtained by including the current job   incl_prof   =   jobs  [  i  ][  2  ]   if   l   !=   -  1  :   incl_prof   +=   DP  [  l  ][  'value'  ]   # Update DP array with the maximum profit and set of jobs   if   incl_prof   >   DP  [  i   -   1  ][  'value'  ]:   DP  .  append  ({  'value'  :   incl_prof     'jobs'  :   DP  [  l  ][  'jobs'  ]   +   [  jobs  [  i  ]]})   else  :   DP  .  append  (  DP  [  i   -   1  ])   # Print the optimal set of jobs and the maximum profit obtained   print  (  'Optimal Jobs for maximum profits are'  )   for   j   in   DP  [  -  1  ][  'jobs'  ]:   print  (  f  '(  {  j  [  0  ]  }     {  j  [  1  ]  }     {  j  [  2  ]  }  )'  )   print  (  f  '  n  Total Optimal profit is   {  DP  [  -  1  ][  'value'  ]  }  '  )   def   latest_non_conflict  (  jobs  :   List  [  Tuple  [  int     int     int  ]]   index  :   int  )   ->   int  :   lo     hi   =   0     index   -   1   while   lo    <=   hi  :   mid   =   (  lo   +   hi  )   //   2   if   jobs  [  mid  ][  1  ]    <=   jobs  [  index  ][  0  ]:   if   jobs  [  mid   +   1  ][  1  ]    <=   jobs  [  index  ][  0  ]:   lo   =   mid   +   1   else  :   return   mid   else  :   hi   =   mid   -   1   return   -  1   # Test the program with a different set of jobs   jobs   =   [(  3     5     20  )   (  1     2     50  )   (  6     19     100  )   (  2     100     200  )]   find_max_profit  (  jobs  )   # This code is contributed by divyansh2212   

   using     System  ;   using     System.Collections.Generic  ;   public     class     WeightedJobScheduling      {      // A job has start time finish time and profit.      class     Job     {      public     int     start       finish       profit  ;      public     Job  (  int     start       int     finish       int     profit  )      {      this  .  start     =     start  ;      this  .  finish     =     finish  ;      this  .  profit     =     profit  ;      }      }      // to store subset of jobs      class     weightedJob         {      // vector of Jobs      public     List   <  Job  >     job  ;      // find profit associated with included Jobs      public     int     value  ;      public     weightedJob  ()     {     job     =     new     List   <  Job  >  ();     }      }      // A utility function that is used for sorting events      // according to finish time      class     JobComparator     :     IComparer   <  Job  >     {      public     int     Compare  (  Job     j1       Job     j2  )      {      return     j1  .  finish     -     j2  .  finish  ;      }      }      // A Binary Search based function to find the latest job      // (before current job) that doesn't conflict with      // current job. 'index' is index of the current job.      // This function returns -1 if all jobs before index      // conflict with it. The array jobs[] is sorted in      // increasing order of finish time      static     int     latestNonConflict  (  Job  []     jobs       int     index  )      {      // Initialize 'lo' and 'hi' for Binary Search      int     lo     =     0       hi     =     index     -     1  ;      // Perform binary Search iteratively      while     (  lo      <=     hi  )     {      int     mid     =     (  lo     +     hi  )     /     2  ;      if     (  jobs  [  mid  ].  finish      <=     jobs  [  index  ].  start  )     {      if     (  jobs  [  mid     +     1  ].  finish       <=     jobs  [  index  ].  start  )     {      lo     =     mid     +     1  ;      }      else     {      return     mid  ;      }      }      else     {      hi     =     mid     -     1  ;      }      }      return     -  1  ;      }      // The main function that finds the subset of jobs      // associated with maximum profit such that no two      // jobs in the subset overlap.      static     int     findMaxProfit  (  Job  []     arr  )      {      // Sort jobs according to finish time      Array  .  Sort  (  arr       new     JobComparator  ());      // Create an array to store solutions of      // subproblems. DP[i] stores the Jobs involved and      // their total profit till arr[i] (including arr[i])      weightedJob  []     DP     =     new     weightedJob  [  arr  .  Length  ];      DP  [  0  ]     =     new     weightedJob  ();      // initialize DP[0] to arr[0]      DP  [  0  ].  value     =     arr  [  0  ].  profit  ;      DP  [  0  ].  job  .  Add  (  arr  [  0  ]);      // Fill entries in DP[] using recursive property      for     (  int     i     =     1  ;     i      <     arr  .  Length  ;     i  ++  )         {      // Find profit including the current job      int     inclProf     =     arr  [  i  ].  profit  ;      int     l     =     latestNonConflict  (  arr       i  );      if     (  l     !=     -  1  )     {      inclProf     +=     DP  [  l  ].  value  ;      }      // Store maximum of including and excluding      if     (  inclProf     >     DP  [  i     -     1  ].  value  )     {      DP  [  i  ]     =     new     weightedJob  ();      DP  [  i  ].  value     =     inclProf  ;      DP  [  i  ].  job  .  AddRange  (  DP  [  l  ].  job  );      DP  [  i  ].  job  .  Add  (  arr  [  i  ]);      }      else     {      DP  [  i  ]     =     DP  [  i     -     1  ];      }      }      // DP[n - 1] stores the result      Console  .  WriteLine  (      'Optimal Jobs for maximum profits are'  );      foreach  (  Job     j     in     DP  [  arr  .  Length     -     1  ].  job  )      {      Console  .  WriteLine  (  '('     +     j  .  start     +     ' '      +     j  .  finish     +     ' '     +     j  .  profit      +     ')'  );      }      Console  .  WriteLine  (  'nTotal Optimal profit is '      +     DP  [  arr  .  Length     -     1  ].  value  );      return     DP  [  arr  .  Length     -     1  ].  value  ;      }      // Driver program      static     void     Main  (  string  []     args  )      {      Job  []     arr      =     {     new     Job  (  3       5       20  )     new     Job  (  1       2       50  )      new     Job  (  6       19       100  )     new     Job  (  2       100       200  )     };      findMaxProfit  (  arr  );      }   }   // This code is contributed by lokeshpotta20.   

   const     findMaxProfit     =     (  jobs  )     =>     {      // Store the number of jobs      const     n     =     jobs  .  length  ;      // Sort the jobs in ascending order of their finish times      jobs  .  sort  ((  a       b  )     =>     a  [  1  ]     -     b  [  1  ]);      // Initialize DP array with the first job and its profit as the maximum profit      let     DP     =     [{     value  :     jobs  [  0  ][  2  ]     jobs  :     [  jobs  [  0  ]]     }];      // Iterate over the remaining jobs      for     (  let     i     =     1  ;     i      <     n  ;     i  ++  )     {      // Find the index of the latest non-conflicting job      const     l     =     latestNonConflict  (  jobs       i  );      // Calculate the profit that can be obtained by including the current job      let     inclProf     =     jobs  [  i  ][  2  ];      if     (  l     !==     -  1  )     {      inclProf     +=     DP  [  l  ].  value  ;      }      // Update DP array with the maximum profit and set of jobs      if     (  inclProf     >     DP  [  i     -     1  ].  value  )     {      DP  .  push  ({     value  :     inclProf       jobs  :     DP  [  l  ].  jobs  .  concat  ([  jobs  [  i  ]])     });      }     else     {      DP  .  push  (  DP  [  i     -     1  ]);      }      }      // Print the optimal set of jobs and the maximum profit obtained      console  .  log  (  'Optimal Jobs for maximum profits are'  );      for     (  const     j     of     DP  [  DP  .  length     -     1  ].  jobs  )     {      console  .  log  (  `(  ${  j  [  0  ]  }     ${  j  [  1  ]  }     ${  j  [  2  ]  }  )`  );      }      console  .  log  (  `nTotal Optimal profit is   ${  DP  [  DP  .  length     -     1  ].  value  }  `  );   };   const     latestNonConflict     =     (  jobs       index  )     =>     {      let     lo     =     0  ;      let     hi     =     index     -     1  ;      while     (  lo      <=     hi  )     {      const     mid     =     Math  .  floor  ((  lo     +     hi  )     /     2  );      if     (  jobs  [  mid  ][  1  ]      <=     jobs  [  index  ][  0  ])     {      if     (  jobs  [  mid     +     1  ][  1  ]      <=     jobs  [  index  ][  0  ])     {      lo     =     mid     +     1  ;      }     else     {      return     mid  ;      }      }     else     {      hi     =     mid     -     1  ;      }      }      return     -  1  ;   };   // Test the program with a different set of jobs   const     jobs     =     [[  3       5       20  ]     [  1       2       50  ]     [  6       19       100  ]     [  2       100       200  ]];   findMaxProfit  (  jobs  );   // This code is contributed by unstoppablepandu.