// 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 aren' ;  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 << 'nTotal 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'nTotal 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.