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

  1. Sort the jobs for their profit in descending order.
  2. 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).
  3. 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).
  4. 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.
  5. Repeat the process for every job.
  6. 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();
    }
}

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.

Leave a Reply