// C++ program for weighted job scheduling using LIS #include    #include  #include    using namespace std; // A job has start time finish time and profit. struct Job {  int start finish profit; }; // Utility function to calculate sum of all vector // elements int findSum(vector<Job> arr) {  int sum = 0;  for (int i = 0; i < arr.size(); i++)  sum += arr[i].profit;  return sum; } // comparator function for sort function int compare(Job x Job y) {  return x.start < y.start; } // The main function that finds the maximum possible // profit from given array of jobs void findMaxProfit(vector<Job> &arr) {  // Sort arr[] by start time.  sort(arr.begin() arr.end() compare);  // L[i] stores Weighted Job Scheduling of  // job[0..i] that ends with job[i]  vector<vector<Job>> 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] = {MaxSum(L[j])} + arr[i] where j < i  // and arr[j].finish <= arr[i].start  if ((arr[j].finish <= arr[i].start) &&  (findSum(L[j]) > findSum(L[i])))  L[i] = L[j];  }  L[i].push_back(arr[i]);  }  vector<Job> maxChain;  // find one with max profit  for (int i = 0; i < L.size(); i++)  if (findSum(L[i]) > findSum(maxChain))  maxChain = L[i];  for (int i = 0; i < maxChain.size(); i++)  cout << '(' << maxChain[i].start << ' ' <<  maxChain[i].finish << ' '  << maxChain[i].profit << ') '; } // Driver Function int main() {  Job a[] = { {3 10 20} {1 2 50} {6 19 100}  {2 100 200} };  int n = sizeof(a) / sizeof(a[0]);  vector<Job> arr(a a + n);  findMaxProfit(arr);  return 0; } 

// Java program for weighted job  // scheduling using LIS import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; class Graph{ // 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;  } }; // Utility function to calculate sum of all // ArrayList elements static int findSum(ArrayList<Job> arr)  {  int sum = 0;    for(int i = 0; i < arr.size(); i++)  sum += arr.get(i).profit;    return sum; } // The main function that finds the maximum // possible profit from given array of jobs static void findMaxProfit(ArrayList<Job> arr) {    // Sort arr[] by start time.  Collections.sort(arr new Comparator<Job>()   {  @Override  public int compare(Job x Job y)   {  return x.start - y.start;  }  });    // sort(arr.begin() arr.end() compare);  // L[i] stores Weighted Job Scheduling of  // job[0..i] that ends with job[i]  ArrayList<ArrayList<Job>> L = new ArrayList<>();  for(int i = 0; i < arr.size(); i++)  {  L.add(new ArrayList<>());  }  // L[0] is equal to arr[0]  L.get(0).add(arr.get(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] = {MaxSum(L[j])} + arr[i] where j < i  // and arr[j].finish <= arr[i].start  if ((arr.get(j).finish <= arr.get(i).start) &&  (findSum(L.get(j)) > findSum(L.get(i))))  {  ArrayList<Job> copied = new ArrayList<>(  L.get(j));  L.set(i copied);  }  }  L.get(i).add(arr.get(i));  }  ArrayList<Job> maxChain = new ArrayList<>();  // Find one with max profit  for(int i = 0; i < L.size(); i++)  if (findSum(L.get(i)) > findSum(maxChain))  maxChain = L.get(i);  for(int i = 0; i < maxChain.size(); i++)   {  System.out.printf('(%d %d %d)n'   maxChain.get(i).start   maxChain.get(i).finish  maxChain.get(i).profit);  } } // Driver code public static void main(String[] args) {  Job[] a = { new Job(3 10 20)   new Job(1 2 50)  new Job(6 19 100)  new Job(2 100 200) };  ArrayList<Job> arr = new ArrayList<>(  Arrays.asList(a));  findMaxProfit(arr); } } // This code is contributed by sanjeev2552 

# Python program for weighted job scheduling using LIS import sys # A job has start time finish time and profit. class Job: def __init__(self start finish profit): self.start = start self.finish = finish self.profit = profit # Utility function to calculate sum of all vector elements def findSum(arr): sum = 0 for i in range(len(arr)): sum += arr[i].profit return sum # comparator function for sort function def compare(x y): if x.start < y.start: return -1 elif x.start == y.start: return 0 else: return 1 # The main function that finds the maximum possible profit from given array of jobs def findMaxProfit(arr): # Sort arr[] by start time. arr.sort(key=lambda x: x.start) # L[i] stores Weighted Job Scheduling of job[0..i] that ends with job[i] L = [[] for _ 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] = {MaxSum(L[j])} + arr[i] where j < i # and arr[j].finish <= arr[i].start if arr[j].finish <= arr[i].start and findSum(L[j]) > findSum(L[i]): L[i] = L[j][:] L[i].append(arr[i]) maxChain = [] # find one with max profit for i in range(len(L)): if findSum(L[i]) > findSum(maxChain): maxChain = L[i] for i in range(len(maxChain)): print('({} {} {})'.format( maxChain[i].start maxChain[i].finish maxChain[i].profit) end=' ') # Driver Function if __name__ == '__main__': a = [Job(3 10 20) Job(1 2 50) Job(6 19 100) Job(2 100 200)] findMaxProfit(a) 

using System; using System.Collections.Generic; using System.Linq; public class Graph {  // A job has start time finish time  // and profit.  public class Job  {  public int start finish profit;  public Job(int start int finish   int profit)  {  this.start = start;  this.finish = finish;  this.profit = profit;  }  };  // Utility function to calculate sum of all  // ArrayList elements  public static int FindSum(List<Job> arr)   {  int sum = 0;    for(int i = 0; i < arr.Count; i++)  sum += arr.ElementAt(i).profit;    return sum;  }  // The main function that finds the maximum  // possible profit from given array of jobs  public static void FindMaxProfit(List<Job> arr)  {    // Sort arr[] by start time.  arr.Sort((x y) => x.start.CompareTo(y.start));  // L[i] stores Weighted Job Scheduling of  // job[0..i] that ends with job[i]  List<List<Job>> L = new List<List<Job>>();  for(int i = 0; i < arr.Count; i++)  {  L.Add(new List<Job>());  }  // L[0] is equal to arr[0]  L[0].Add(arr[0]);  // 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] = {MaxSum(L[j])} + arr[i] where j < i  // and arr[j].finish <= arr[i].start  if ((arr[j].finish <= arr[i].start) &&  (FindSum(L[j]) > FindSum(L[i])))  {  List<Job> copied = new List<Job>(  L[j]);  L[i] = copied;  }  }  L[i].Add(arr[i]);  }  List<Job> maxChain = new List<Job>();  // Find one with max profit  for(int i = 0; i < L.Count; i++)  if (FindSum(L[i]) > FindSum(maxChain))  maxChain = L[i];  for(int i = 0; i < maxChain.Count; i++)   {  Console.WriteLine('({0} {1} {2})'   maxChain[i].start   maxChain[i].finish  maxChain[i].profit);  }  }  // Driver code  public static void Main(String[] args)  {  Job[] a = { new Job(3 10 20)   new Job(1 2 50)  new Job(6 19 100)  new Job(2 100 200) };  List<Job> arr = new List<Job>(a);  FindMaxProfit(arr);  } } 

// JavaScript program for weighted job scheduling using LIS // A job has start time finish time and profit. function Job(start finish profit) {  this.start = start;  this.finish = finish;  this.profit = profit; } // Utility function to calculate sum of all vector // elements function findSum(arr) {  let sum = 0;  for (let i = 0; i < arr.length; i++) {  sum += arr[i].profit;  }  return sum; } // comparator function for sort function function compare(x y) {  return x.start < y.start; } // The main function that finds the maximum possible // profit from given array of jobs function findMaxProfit(arr) {  // Sort arr[] by start time.  arr.sort(compare);  // L[i] stores Weighted Job Scheduling of  // job[0..i] that ends with job[i]  let L = new Array(arr.length).fill([]);  // L[0] is equal to arr[0]  L[0] = [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] = {MaxSum(L[j])} + arr[i] where j < i  // and arr[j].finish <= arr[i].start  if (arr[j].finish <= arr[i].start && findSum(L[j]) > findSum(L[i])) {  L[i] = L[j];  }  }  L[i].push(arr[i]);  }  let maxChain = [];  // find one with max profit  for (let i = 0; i < L.length; i++) {  if (findSum(L[i]) > findSum(maxChain)) {  maxChain = L[i];  }  }  for (let i = 0; i < maxChain.length; i++) {  console.log(  '(' +  maxChain[i].start +  ' ' +  maxChain[i].finish +  ' ' +  maxChain[i].profit +  ') '  );  } } // Driver Function let a = [  new Job(3 10 20)  new Job(1 2 50)  new Job(2 100 200) ]; findMaxProfit(a);