Summary: In this tutorial, we will learn what the Job Sequencing with Deadlines Problem is and how to solve the Job Sequencing Problem in C, C++, and Java.
The problem of Job sequencing with deadlines can be easily solved using the greedy algorithm.
If you don’t know what is the Greedy algorithm then check this Fractional knapsack problem using the Greedy Algorithm, where I have explained the greedy algorithm with the examples.
What is Job Sequencing with Deadlines Problem?
Suppose you are a freelancer who has got 5 different jobs to do with the respective deadlines and profit/payment. Also, you are not sure whether you will be able to complete all the jobs before the respective deadlines.
So, which job will you start working on first?
- The job which gives you maximum profit: In this case, the job may have a long deadline and by doing this job you may miss some jobs with a short deadline. And it can be unprofitable to you if the sum of profits from missed jobs is greater than the profit of the job which you are doing.
- The job which has a short deadline: In this case, It may happen that you have completed multiple jobs within the given deadlines but there could be the possibility that you could have earned more if you would have chosen the job with max profit.
To solve the ambiguity of which job to choose, we use greedy approach.
Job Sequencing with Deadlines Solution using Greedy Algorithm
- Sort the jobs for their profit in descending order.
- Choose the uncompleted job with high profit (i.e. first job in the array, since the array is sorted). Because it is not necessary to complete the job on the very first date, we will do/complete the job on the last day of the deadline (i.e. Add the job to a new array/list at the index equal to its deadline day).
- Now again choose the next uncompleted high-profit job. Check its deadline. If its deadline is greater than the deadline of the previous chosen job, then we will do/complete this job on the last day of the deadline only if the day is empty, else will do the job on the previous empty day which is nearest to the deadline ( i.e. Add the job to new array/list at the index equal or nearest to its deadline day, only if the array is empty at particular index).
- If you don’t have the empty day before the job deadline (i.e. all the array index is occupied before the
index=job.deadline) then do not do the job. - Repeat the process for every job.
- The final array or list will give the best jobs to do for max profit.
In short, we are being greedy (choosing a job with max profit) and lazy (completing a job on the day of the deadline).
Here is the implementation of the steps in C, C++ and Java:
C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//Job Structure
typedef struct {
char id;
int deadline;
int profit;
}Job;
/* function to compare two jobs based on their profit.
returns true if job b's profit < job a's profit */
int compareJob(const Job *a, const Job *b){
return b->profit - a->profit;
}
//function finds the best job sequence
void bestJob(Job jobs[],int sizeOfJobs){
//null char array
char jobsToDo[5]= {'\0'};
for(int i=0, k=0; i<sizeOfJobs; i++){
k = jobs[i].deadline-1;
//Searching backwards the empty date nearest to deadline
while(jobsToDo[k] != '\0' && k >= 0){
k--;
}
//if empty date found, set the job
if(k != -1)
jobsToDo[k]= jobs[i].id;
}
//output the final job sequence
printf("\nBest order and jobs to do is: ");
int idx=0;
while(jobsToDo[idx] != '\0'){
printf("%c ",jobsToDo[idx]);
idx++;
}
}
//function to display the jobs table
void display(Job jobs[], int n){
printf("Job Id: \t");
for(int i=0; i<n; i++){
printf("%c \t",jobs[i].id);
}
printf("\n");
printf("Job Deadline: \t");
for(int i=0; i<n; i++){
printf("%d \t",jobs[i].deadline);
}
printf("\n");
printf("Job Profit: \t");
for(int i=0; i<n; i++){
printf("%d \t",jobs[i].profit);
}
printf("\n");
}
int main()
{
//intialize the jobs
Job jobs[]= {{'w', 1, 19}, {'v', 2, 100}, {'x', 2, 27},
{'y', 1, 25}, {'z', 3, 15}};
//display the jobs data
display(jobs,5);
//sorting jobs[] w.r.t their profit
qsort(jobs,5,sizeof(jobs[0]),compareJob);
bestJob(jobs,5);
return 0;
}C++
#include <iostream>
#include <algorithm>
using namespace std;
//Job Structure
typedef struct {
char id;
int deadline;
int profit;
}Job;
/* function to compare two jobs based on their profit.
returns true if job b's profit < job a's profit */
bool compareJob(Job a, Job b){
return a.profit > b.profit;
}
//function finds the best job sequence
void bestJob(Job jobs[],int sizeOfJobs){
//null char array
char jobsToDo[5]= {'\0'};
for(int i=0, k=0; i<sizeOfJobs; i++){
k = jobs[i].deadline-1;
//Searching backwards the empty date nearest to deadline
while(jobsToDo[k] != '\0' && k >= 0){
k--;
}
//if empty date found, set the job
if(k != -1)
jobsToDo[k]= jobs[i].id;
}
//output the final job sequence
cout << "\nBest order and jobs to do is: ";
int idx=0;
while(jobsToDo[idx] != '\0'){
cout << "\t" << jobsToDo[idx];
idx++;
}
}
//function to display the jobs table
void display(Job jobs[],int n){
cout << "Job Id: \t";
for(int i=0; i<n; i++){
cout << jobs[i].id << "\t";
}
cout << endl;
cout << "Job Deadline: \t";
for(int i=0; i<n; i++){
cout << jobs[i].deadline << "\t";
}
cout << endl;
cout << "Job Profit: \t";
for(int i=0; i<n; i++){
cout << jobs[i].profit << "\t";
}
cout << endl;
}
int main()
{
//intialize the jobs
Job jobs[]= {{'w', 1, 19}, {'v', 2, 100}, {'x', 2, 27},
{'y', 1, 25}, {'z', 3, 15}};
//display the jobs data
display(jobs, 5);
//sorting jobs[] w.r.t profit
sort(jobs,jobs+5,compareJob);
//call the job sequencing method
bestJob(jobs,5);
return 0;
}Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Job implements Comparable<Job>{
char id;
int deadline;
int profit;
public Job(char id, int deadline, int profit) {
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
/* function to compare two jobs based on their profits.
returns true if job b's profit < job a's profit */
@Override
public int compareTo( Job b) {
return b.profit - this.profit;
}
}
class JobSequencing {
List<Job> jobs;
public JobSequencing(List<Job> jobs) {
this.jobs = jobs;
}
//function finds the best job sequence
void bestJob() {
char jobsToDo[] = new char[5];
int k;
for (Job job : jobs) {
k = job.deadline - 1;
//Searching backwards the empty date nearest to deadline
while ( k >= 0 && jobsToDo[k] != '\0' ) {
k--;
}
//if empty date found, set the job
if (k != -1)
jobsToDo[k] = job.id;
}
//output the final job sequence
System.out.print("Best order and jobs to do is: ");
k = 0;
while (jobsToDo[k] != '\0') {
System.out.print(jobsToDo[k] + " ");
k++;
}
}
//function to display the jobs table
void display(){
System.out.print("Job Id: \t");
for(Job job : jobs){
System.out.print(job.id +"\t");
}
System.out.println();
System.out.print("Job Deadline: \t");
for(Job job : jobs){
System.out.print(job.deadline +"\t");
}
System.out.println();
System.out.print("Job Profit: \t");
for(Job job : jobs){
System.out.print(job.profit +"\t");
}
System.out.println();
}
}
class Main {
public static void main(String[] args){
//intialize the jobs
List<Job> jobs= new ArrayList<>();
jobs.add(new Job('w', 1, 19));
jobs.add(new Job('v', 2, 100));
jobs.add(new Job('x', 2, 27));
jobs.add(new Job('y', 1, 25));
jobs.add(new Job('z', 3, 15));
//display the jobs data
JobSequencing js = new JobSequencing(jobs);
js.display();
//sorting jobs[] w.r.t profit
Collections.sort(jobs);
//call the job sequencing method
js.bestJob();
}
}Python
from typing import List
class Job:
def __init__(self, id: str, deadline: int, profit: int):
#initialize the job's id, deadline, and profit
self.id = id
self.deadline = deadline
self.profit = profit
# define comparison between two jobs based on their profits
def __lt__(self, other):
return self.profit > other.profit
class JobSequencing:
def __init__(self, jobs: List[Job]):
self.jobs = jobs
# function finds the best job sequence
def best_job(self):
jobs_to_do = ['' for _ in range(5)]
k = 0
#searching backwards the empty date nearest to deadline
for job in self.jobs:
k = job.deadline - 1
while k >= 0 and jobs_to_do[k] != '':
k -= 1
#if empty date found, set the job
if k != -1:
jobs_to_do[k] = job.id
#output the final job sequence
print("Best order and jobs to do is: ", end='')
k = 0
while jobs_to_do[k] != '':
print(jobs_to_do[k], end=' ')
k += 1
#function to display the jobs table
def display(self):
print("Job Id: \t", end='')
for job in self.jobs:
print(job.id, end='\t')
print()
print("Job Deadline: \t", end='')
for job in self.jobs:
print(job.deadline, end='\t')
print()
print("Job Profit: \t", end='')
for job in self.jobs:
print(job.profit, end='\t')
print()
if __name__ == "__main__":
#intialize the jobs
jobs = [
Job('w', 1, 19),
Job('v', 2, 100),
Job('x', 2, 27),
Job('y', 1, 25),
Job('z', 3, 15)
]
js = JobSequencing(jobs)
#display the jobs data
js.display()
#sorting jobs[] w.r.t profit
jobs.sort()
#call the job sequencing method
js.best_job()
Output:
Job Id: w v x y z Job Deadline: 1 2 2 1 3 Job Profit: 19 100 27 25 15 Best order and jobs to do is x v z
In this tutorial, we learned what the Job Sequencing with Deadlines Problem is and how to solve Job sequencing problem in C, C++, and Java programming languages.