Job sequencing problem using Priority-Queue (Max-Heap)

Sort the jobs in the increasing order of their deadlines and then calculate the available slots between every two consecutive deadlines while iterating from the end. Include the profit of the job at the root of the Max-Heap while the empty slots are available and Heap is not empty, as this would help to choose the jobs with maximum profit for every set of available slots.

Follow the given steps to solve the problem:

Sort the jobs based on their deadlines.
Iterate from the end and calculate the available slots between every two consecutive deadlines. Insert the profit, deadline, and job ID of ith job in the max heap.
While the slots are available and there are jobs left in the max heap, include the job ID with maximum profit and deadline in the result.
Sort the result array based on their deadlines.

Below is the implementation of the above approach:

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// A structure to represent a job
struct Job {
   
    char id; // Job Id
    int dead; // Deadline of job
    int profit; // Profit earned if job is completed before
                // deadline
};
 
// Custom sorting helper struct which is used for sorting
// all jobs according to profit
struct jobProfit {
    bool operator()(Job const& a, Job const& b)
    {
        return (a.profit < b.profit);
    }
};
 
// Returns maximum profit from jobs
void printJobScheduling(Job arr[], int n)
{
    vector<Job> result;
    sort(arr, arr + n,
         [](Job a, Job b) { return a.dead < b.dead; });
   
    // set a custom priority queue
    priority_queue<Job, vector<Job>, jobProfit> pq;
   
    for (int i = n - 1; i >= 0; i--) {
        int slot_available;
       
        // we count the slots available between two jobs
        if (i == 0) {
            slot_available = arr[i].dead;
        }
        else {
            slot_available = arr[i].dead - arr[i - 1].dead;
        }
       
        // include the profit of job(as priority),
        // deadline and job_id in maxHeap
        pq.push(arr[i]);
       
        while (slot_available > 0 && pq.size() > 0) {
           
            // get the job with the most profit
            Job job = pq.top();
            pq.pop();
           
            // reduce the slots
            slot_available--;
           
            // add it to the answer
            result.push_back(job);
        }
    }
   
    // sort the result based on the deadline
    sort(result.begin(), result.end(),
         [&](Job a, Job b) { return a.dead < b.dead; });
   
    // print the result
    for (int i = 0; i < result.size(); i++)
        cout << result[i].id << ' ';
    cout << endl;
}
 
// Driver's code
int main()
{
    Job arr[] = { { 'a', 2, 100 },
                  { 'b', 1, 19 },
                  { 'c', 2, 27 },
                  { 'd', 1, 25 },
                  { 'e', 3, 15 } };
   
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Following is maximum profit sequence of jobs "
            "\n";
 
    // Function call
    printJobScheduling(arr, n);
    return 0;
}
 
// This code is contributed By Reetu Raj Dubey

Java

// Java implementation of above approach
 
// Program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.*;
 
public class GFG {
 
    // a class to represent job
    static class Job {
        char job_id;
        int deadline;
        int profit;
        Job(char job_id, int deadline, int profit)
        {
            this.deadline = deadline;
            this.job_id = job_id;
            this.profit = profit;
        }
    }
 
    static void printJobScheduling(ArrayList<Job> arr)
    {
        int n = arr.size();
 
        // sorting the array on the
        // basis of their deadlines
        Collections.sort(arr, (a, b) -> {
            return a.deadline - b.deadline;
        });
 
        // initialise the result array and maxHeap
        ArrayList<Job> result = new ArrayList<>();
        PriorityQueue<Job> maxHeap = new PriorityQueue<>(
            (a, b) -> { return b.profit - a.profit; });
 
        // starting the iteration from the end
        for (int i = n - 1; i > -1; i--) {
            int slot_available;
           
            // calculate slots between two deadlines
            if (i == 0) {
                slot_available = arr.get(i).deadline;
            }
            else {
                slot_available = arr.get(i).deadline
                                 - arr.get(i - 1).deadline;
            }
 
            // include the profit of job(as priority),
            // deadline and job_id in maxHeap
            maxHeap.add(arr.get(i));
 
            while (slot_available > 0
                   && maxHeap.size() > 0) {
 
                // get the job with max_profit
                Job job = maxHeap.remove();
 
                // reduce the slots
                slot_available--;
 
                // include the job in the result array
                result.add(job);
            }
        }
 
        // jobs included might be shuffled
        // sort the result array by their deadlines
        Collections.sort(result, (a, b) -> {
            return a.deadline - b.deadline;
        });
       
        for (Job job : result) {
            System.out.print(job.job_id + " ");
        }
       
        System.out.println();
    }
 
    // Driver's Code
    public static void main(String[] args)
    {
        ArrayList<Job> arr = new ArrayList<Job>();
 
        arr.add(new Job('a', 2, 100));
        arr.add(new Job('b', 1, 19));
        arr.add(new Job('c', 2, 27));
        arr.add(new Job('d', 1, 25));
        arr.add(new Job('e', 3, 15));
       
        System.out.println("Following is maximum "
                           + "profit sequence of jobs");
 
        // Function call
        printJobScheduling(arr);
    }
}
 
// This code is contributed by Karandeep Singh

Python3

# Python3 program for the above approach 
import heapq
 
 
def printJobScheduling(arr):
    n = len(arr)
 
    # arr[i][0] = job_id, arr[i][1] = deadline, arr[i][2] = profit
 
    # sorting the array on the
    # basis of their deadlines
    arr.sort(key=lambda x: x[1])
 
    # initialise the result array and maxHeap
    result = []
    maxHeap = []
 
    # starting the iteration from the end
    for i in range(n - 1, -1, -1):
 
        # calculate slots between two deadlines
        if i == 0:
            slots_available = arr[i][1]
        else:
            slots_available = arr[i][1] - arr[i - 1][1]
 
        # include the profit of job(as priority), deadline
        # and job_id in maxHeap
        # note we push negative value in maxHeap to convert
        # min heap to max heap in python
        heapq.heappush(maxHeap, (-arr[i][2], arr[i][1], arr[i][0]))
 
        while slots_available and maxHeap:
 
            # get the job with max_profit
            profit, deadline, job_id = heapq.heappop(maxHeap)
 
            # reduce the slots
            slots_available -= 1
 
            # include the job in the result array
            result.append([job_id, deadline])
 
    # jobs included might be shuffled
    # sort the result array by their deadlines
    result.sort(key=lambda x: x[1])
 
    for job in result:
        print(job[0], end=" ")
    print()
 
 
# Driver's Code
if __name__ == '__main__':
    arr = [['a', 2, 100],  # Job Array
           ['b', 1, 19],
           ['c', 2, 27],
           ['d', 1, 25],
           ['e', 3, 15]]
 
    print("Following is maximum profit sequence of jobs")
 
    # Function Call
    printJobScheduling(arr)
 
# This code is contributed
# by Shivam Bhagat

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
namespace GFG
{
   
  // A class to represent a job
  public class Job
  {
    public char JobId { get; set; }
    public int Deadline { get; set; }
    public int Profit { get; set; }
    public Job(char jobId, int deadline, int profit)
    {
      this.Deadline = deadline;
      this.JobId = jobId;
      this.Profit = profit;
    }
  }
 
  class Scheduling
  {
    static void PrintJobScheduling(List<Job> arr)
    {
      int n = arr.Count;
 
      // Sorting the array based on their deadlines
      arr.Sort((a, b) => b.Deadline.CompareTo(a.Deadline));
 
      // Initializing the result array
      List<Job> result = new List<Job>();
 
      // Starting the iteration from the end
      for (int i = n - 1; i >= 0; i--)
      {
        int slot_available;
 
        // Calculating the slots between two deadlines
        if (i == 0)
        {
          slot_available = arr[i].Deadline;
        }
        else
        {
          slot_available = arr[i].Deadline - arr[i - 1].Deadline;
        }
 
        // Including the job with max profit
        Job job = null;
        int maxProfit = -1;
        for (int j = i; j >= 0; j--)
        {
          if (arr[j].Deadline >= slot_available && arr[j].Profit > maxProfit)
          {
            job = arr[j];
            maxProfit = arr[j].Profit;
          }
        }
 
        if (job != null)
        {
          slot_available--;
          result.Add(job);
          arr.Remove(job);
          i--;
        }
      }
 
      // Jobs included might be shuffled
      // Sorting the result array based on their deadlines
      result.Sort((a, b) => a.Deadline.CompareTo(b.Deadline));
 
      foreach (Job job in result)
      {
        Console.Write(job.JobId + " ");
      }
      Console.WriteLine();
    }
 
    // Driver Code
    static void Main(string[] args)
    {
      List<Job> arr = new List<Job>
      {
        new Job('a', 2, 100),
        new Job('b', 1, 19),
        new Job('c', 2, 27),
        new Job('d', 1, 25),
        new Job('e', 3, 15)
        };
 
      Console.WriteLine("Following is maximum profit sequence of jobs");
 
      // Function call
      PrintJobScheduling(arr);
    }
  }
}
 
// This code is contributed by phasing17.

Javascript

// JS implementation of the above approach
 
// A class to represent a job
class Job {
constructor(jobId, deadline, profit) {
this.JobId = jobId;
this.Deadline = deadline;
this.Profit = profit;
}
}
 
function PrintJobScheduling(arr) {
  let n = arr.length;
 
  // Sorting the array based on their deadlines
  arr.sort((a, b) => b.Deadline - a.Deadline);
 
  // Initializing the result array
  let result = [];
 
  // Starting the iteration from the end
  let i;
  for (i = n - 1; i >= 0; i--) {
    let slot_available;
 
    // Calculating the slots between two deadlines
    if (i == 0) {
      slot_available = arr[i].Deadline;
    } else {
      slot_available = arr[i].Deadline - arr[i - 1].Deadline;
    }
 
    // Including the job with max profit
    let job ;
    let maxProfit = -1;
    for (let j = i; j >= 0; j--) {
      if (arr[j].Deadline >= slot_available && arr[j].Profit > maxProfit) {
        job = arr[j];
        maxProfit = arr[j].Profit;
      }
    }
 
    if (job != null) {
      slot_available--;
      result.push(job);
      arr.splice(arr.indexOf(job), 1);
      i--;
      // Remove the job from the input list
    }
  }
 
  // Jobs included might be shuffled
  // Sorting the result array based on their deadlines
  result.sort((a, b) => a.Deadline - b.Deadline);
 
  const output = result.map(job => job.JobId).join(" ");
  console.log(output);
}
 
 
 
// Driver Code
let arr = [
new Job('a', 2, 100),
new Job('b', 1, 19),
new Job('c', 2, 27),
new Job('d', 1, 25),
new Job('e', 3, 15)
];
 
console.log("Following is maximum profit sequence of jobs");
 
// Function call
PrintJobScheduling(arr);
 
// This code is contributed by phasing17.

Output

Following is maximum profit sequence of jobs
a c e

Time Complexity: O(N log N)
Auxiliary Space: O(N)

It can also be optimized using Disjoint Set Data Structure. Please refer to the below post for details.
Job Sequencing Problem | Set 2 (Using Disjoint Set)

Job Sequencing Problem

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. Maximize the total profit if only one job can be scheduled at a time.

Examples:

Input: Four Jobs with following deadlines and profits

JobID Deadline Profit

a 4 20
b 1 10
c 1 40
d 1 30

Output: Following is maximum profit sequence of jobs: c, a

Input: Five Jobs with following deadlines and profits

JobID Deadline Profit

a 2 100
b 1 19
c 2 27
d 1 25
e 3 15

Output: Following is maximum profit sequence of jobs: c, a, e

Naive Approach: To solve the problem follow the below idea:

Generate all subsets of a given set of jobs and check individual subsets for the feasibility of jobs in that subset. Keep track of maximum profit among all feasible subsets.

Job sequencing problem using Priority-Queue (Max-Heap)

C++

Java

Python3

C#

Javascript

Job Sequencing Problem

Categories

Contact US

Job sequencing problem using Priority-Queue (Max-Heap)

C++

Java

Python3

C#

Javascript

Job Sequencing Problem

Similar Reads

Categories

Contact US