View Discussion
Improve Article
Save Article
ReadDiscussView Discussion
Improve Article
Save Article
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.
Greedy approach for job sequencing problem:
Greedily choose the jobs with maximum profit first, by sorting the
jobs in decreasing order of their profit. This would help to maximize the total profit as choosing the job with maximum profit for every time slot will eventually maximize the total profit
Follow the given steps to solve the problem:
- Sort all jobs in decreasing order of profit.
- Iterate on jobs in decreasing order of profit.For each job , do the following :
- Find a time slot i, such that slot is empty and i < deadline and i
is greatest.Put the job in
this slot and mark this slot filled. - If no such i exists, then ignore the job.
Below is the implementation of the above approach:
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Job {
char id;
int dead;
int profit;
} Job;
int compare(const void* a, const
void* b)
{
Job* temp1 = (Job*)a;
Job* temp2 = (Job*)b;
return (temp2->profit - temp1->profit);
}
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
void printJobScheduling(Job arr[], int n)
{
qsort(arr, n, sizeof(Job), compare);
int result[n];
bool slot[n];
for (int i = 0; i < n; i++)
slot[i] = false;
for (int i = 0; i < n; i++) {
for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
if (slot[j] == false) {
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i = 0; i < n; i++)
if (slot[i])
printf("%c ", arr[result[i]].id);
}
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]);
printf(
"Following is maximum profit sequence of jobs \n");
printJobScheduling(arr, n);
return 0;
}
C++
#include <algorithm>
#include <iostream>
using namespace std;
struct Job {
char
id;
int dead;
int profit;
};
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
void printJobScheduling(Job arr[], int n)
{
sort(arr, arr + n, comparison);
int result[n];
bool slot[n];
for (int i = 0; i < n; i++)
slot[i] = false;
for (int i = 0; i < n; i++) {
for (int
j = min(n, arr[i].dead) - 1; j >= 0; j--) {
if (slot[j] == false) {
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i = 0; i < n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}
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";
printJobScheduling(arr, n);
return 0;
}
Java
import java.util.*;
class Job {
char id;
int deadline, profit;
public
Job() {}
public Job(char id, int deadline, int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
void printJobScheduling(ArrayList<Job> arr, int t)
{
int n = arr.size();
Collections.sort(arr,
(a, b) -> b.profit - a.profit);
boolean result[] = new boolean[t];
char job[] = new
char[t];
for (int i = 0; i < n; i++) {
for (int j
= Math.min(t - 1, arr.get(i).deadline - 1);
j >= 0; j--) {
if (result[j] == false) {
result[j] = true;
job[j] = arr.get(i).id;
break;
}
}
}
for (char
jb : job)
System.out.print(jb + " ");
System.out.println();
}
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");
Job job = new Job();
job.printJobScheduling(arr, 3);
}
}
Python3
def printJobScheduling(arr, t):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j][2] < arr[j + 1][2]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
result = [False] * t
job = ['-1'] * t
for i in range(len(arr)):
for
j in range(min(t - 1, arr[i][1] - 1), -1, -1):
if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break
print(job)
if __name__ == '__main__':
arr =
[['a', 2, 100],
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]
print("Following is maximum profit sequence of jobs")
printJobScheduling(arr, 3)
C#
using System;
using System.Collections.Generic;
class GFG : IComparer<Job> {
public int Compare(Job x, Job y)
{
if (x.profit == 0 || y.profit == 0) {
return 0;
}
return (y.profit).CompareTo(x.profit);
}
}
public class Job {
char id;
public int deadline, profit;
public Job() {}
public Job(char
id, int deadline, int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
void printJobScheduling(List<Job> arr, int t)
{
int n = arr.Count;
GFG gg = new GFG();
arr.Sort(gg);
bool[] result = new bool[t];
char[] job = new char[t];
for
(int i = 0; i < n; i++) {
for (int j
= Math.Min(t - 1, arr[i].deadline - 1);
j >= 0; j--) {
if (result[j] == false) {
result[j] = true;
job[j] = arr[i].id;
break;
}
}
}
foreach(char jb in job) { Console.Write(jb + " "); }
Console.WriteLine();
}
static public void
Main()
{
List<Job> arr = new List<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));
Console.WriteLine("Following is maximum "
+ "profit sequence of jobs");
Job job = new Job();
job.printJobScheduling(arr, 3);
}
}
Javascript
function printJobScheduling(arr, t){
let n = arr.length;
for(let i=0;i<n;i++){
for(let j = 0;j<(n - 1 - i);j++){
if(arr[j][2] < arr[j + 1][2]){
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
let result = [];
let job = [];
for(let i = 0;i<t;i++){
job[i] = '-1';
result[i] = false;
}
for(let i= 0;i<arr.length;i++){
for(let j = (t - 1, arr[i][1] - 1);j>=0;j--){
if(result[j] == false){
result[j] = true;
job[j] = arr[i][0];
break;
}
}
}
document.write(job);
}
arr = [['a', 2, 100],
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]];
document.write("Following is maximum profit sequence of jobs ");
document.write("<br>");
printJobScheduling(arr, 3) ;
Output
Following is maximum profit sequence of jobs
c a e
Time Complexity: O(N2)
Auxiliary Space: O(N)
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++
#include <bits/stdc++.h>
using namespace std;
struct Job {
char id;
int dead;
int profit;
};
struct
jobProfit {
bool operator()(Job const& a, Job const& b)
{
return (a.profit < b.profit);
}
};
void printJobScheduling(Job arr[], int n)
{
vector<Job> result;
sort(arr, arr + n,
[](Job a, Job b) { return a.dead < b.dead; });
priority_queue<Job, vector<Job>, jobProfit> pq;
for (int i = n - 1; i >= 0; i--) {
int slot_available;
if (i == 0) {
slot_available = arr[i].dead;
}
else
{
slot_available = arr[i].dead - arr[i - 1].dead;
}
pq.push(arr[i]);
while (slot_available > 0 && pq.size() > 0) {
Job job = pq.top();
pq.pop();
slot_available--;
result.push_back(job);
}
}
sort(result.begin(), result.end(),
[&](Job a, Job b) { return a.dead < b.dead; });
for (int i = 0; i < result.size(); i++)
cout << result[i].id << ' ';
cout << endl;
}
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";
printJobScheduling(arr, n);
return 0;
}
Java
import java.util.*;
class GFG {
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();
Collections.sort(arr, (a, b) -> {
return a.deadline - b.deadline;
});
ArrayList<Job> result = new
ArrayList<>();
PriorityQueue<Job> maxHeap = new PriorityQueue<>(
(a, b) -> { return b.profit - a.profit; });
for (int i = n - 1; i > -1; i--) {
int slot_available;
if (i == 0) {
slot_available = arr.get(i).deadline;
}
else {
slot_available = arr.get(i).deadline
- arr.get(i - 1).deadline;
}
maxHeap.add(arr.get(i));
while (slot_available > 0
&& maxHeap.size() > 0) {
Job job = maxHeap.remove();
slot_available--;
result.add(job);
}
}
Collections.sort(result, (a, b) -> {
return a.deadline - b.deadline;
});
for (Job job : result) {
System.out.print(job.job_id + " ");
}
System.out.println();
}
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");
printJobScheduling(arr);
}
}
Python3
import heapq
def printJobScheduling(arr):
n = len(arr)
arr.sort(key=lambda x: x[1])
result = []
maxHeap = []
for i in range(n - 1, -1, -1):
if
i == 0:
slots_available = arr[i][1]
else:
slots_available = arr[i][1] - arr[i - 1][1]
heapq.heappush(maxHeap, (-arr[i][2], arr[i][1], arr[i][0]))
while slots_available and maxHeap:
profit, deadline, job_id = heapq.heappop(maxHeap)
slots_available -= 1
result.append([job_id, deadline])
result.sort(key=lambda
x: x[1])
for job in result:
print(job[0], end=" ")
print()
if __name__ == '__main__':
arr = [['a', 2, 100],
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]
print("Following is maximum profit sequence of jobs")
printJobScheduling(arr)
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)
This article is contributed by Shubham. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Solution. To solve this problem, the given jobs are sorted according to their profit in a descending order. Hence, after sorting, the jobs are ordered as shown in the following table. From this set of jobs, first we select J2, as it can be completed within its deadline and contributes maximum profit.
In a job sequencing with deadlines problem, the objective is to find a sequence of jobs completed within their deadlines, giving a maximum profit. Let us consider the set of n given jobs associated with deadlines, and profit is earned if a job is completed by its deadline.
Given a set of 9 jobs where each job has a deadline and profit associated to it . Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline.
Since the scheduling may be done by using the rules of jobs and orders, two types of scheduling methodologies are created namely job-based rule and order-based rule.
