Weighted Job Scheduling | Set 2 (Using LIS)

22 August 2024

2

Given N jobs where every job is represented by following three elements of it.
1. Start Time
2. Finish Time
3. Profit or Value Associated
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Examples:

Input:  
Number of Jobs n = 4
Job Details {Start Time, Finish Time, Profit}
Job 1: {1, 2, 50}
Job 2: {3, 5, 20}
Job 3: {6, 19, 100}
Job 4: {2, 100, 200}

Output:  
Job 1: {1, 2, 50}
Job 4: {2, 100, 200}

Explanation: We can get the maximum profit by 
scheduling jobs 1 and 4 and maximum profit is 250.

In previous post, we have discussed about Weighted Job Scheduling problem. We discussed a DP solution where we basically includes or excludes current job. In this post, another interesting DP solution is discussed where we also print the Jobs. This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. We need a slight change in the Dynamic Programming solution of LIS problem.

We first need to sort jobs according to start time. Let job[0..n-1] be the array of jobs after sorting. We define vector L such that L[i] is itself is a vector that stores Weighted Job Scheduling of job[0..i] that ends with job[i]. Therefore for an index i, L[i] can be recursively written as –

L[0] = {job[0]}
L[i] = {MaxSum(L[j])} + job[i] where j < i and job[j].finish <= job[i].start
     = job[i], if there is no such j

For example, consider pairs {3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}

After sorting we get, 
{1, 2, 50}, {2, 100, 200}, {3, 10, 20}, {6, 19, 100}

Therefore,
L[0]: {1, 2, 50}
L[1]: {1, 2, 50} {2, 100, 200}
L[2]: {1, 2, 50} {3, 10, 20}
L[3]: {1, 2, 50} {6, 19, 100}

We choose the vector with highest profit. In this case, L[1].

Below is the implementation of the above idea –

C++

// C++ program for weighted job scheduling using LIS
#include <iostream>
#include <vector>
#include <algorithm>
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

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

Javascript

// 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);

C#

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);
    }
}

Python3

# 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)

Output

(1, 2, 50) (2, 100, 200)

We can further optimize the above DP solution by removing findSum() function. Instead, we can maintain another vector/array to store sum of maximum profit possible till job i. The implementation can be seen here.

Time complexity of above Dynamic Programming solution is O(n²) where n is the number of Jobs.
Auxiliary space used by the program is O(n²).

This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Weighted Job Scheduling | Set 2 (Using LIS)

C++

Java

Javascript

C#

Python3

Java Program for Longest Common Subsequence

Maximum height of Tree when any Node can be considered as Root

Print Fibonacci sequence using 2 variables

LEAVE A REPLY Cancel reply

Most Popular

5 Best VPNs for New Zealand in 2025: Stream Freely & Safely by Raven Wu

Samsung Galaxy S25 leak shows off blue colorway and MagSafe-style case options

Weekend poll: How long do you plan on keeping your current smartphone?

Android 15 arrives on the Nothing Phone 2a Plus ahead of several flagships

Recent Comments

EDITOR PICKS

5 Best VPNs for New Zealand in 2025: Stream Freely & Safely by Raven Wu

Samsung Galaxy S25 leak shows off blue colorway and MagSafe-style case options

Weekend poll: How long do you plan on keeping your current smartphone?

POPULAR POSTS

5 Best VPNs for New Zealand in 2025: Stream Freely & Safely by Raven Wu

Samsung Galaxy S25 leak shows off blue colorway and MagSafe-style case options

Weekend poll: How long do you plan on keeping your current smartphone?

POPULAR CATEGORY

ABOUT US

FOLLOW US