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>
 
typedef struct {
    char id;
    int deadline;
    int profit;
 
}Job;
 
int compareJob(const void *a, const void *b){
    //Will return true if a's profit > b's profit
    //else will return false
    return ((Job*)a)->profit - ((Job*)a)->profit;
}
 
void bestJob(Job jobs[],int sizeOfJobs){
    char jobsToDo[5]= {'\0'}; //Assign every element of array to '\0'-Only works in few compilers
    //If above line do not work use for loop to assign '\0' to every element
    int i, k;
    for(i=0; i< sizeOfJobs; i++){
            k= jobs[i].deadline-1;
        //Searching for empty date nearest to deadline backwards
        while(jobsToDo[k] != '\0' && k >= 0){
            k--;
        }
        if(k != -1)
            jobsToDo[k]= jobs[i].id;
    }
    printf("Best order and jobs to do is \n");
    k=0;
    while(jobsToDo[k] != '\0'){
        printf("%c ",jobsToDo[k]);
        k++;
    }
}
 
void display(Job jobs[],int n){
    int i;
    printf("Job Id: \t");
    for(i=0; i<n; i++){
        printf("%c \t",jobs[i].id);
    }
    printf("\n");
 
    printf("Job Deadline: \t");
    for(i=0; i<n; i++){
        printf("%d \t",jobs[i].deadline);
    }
    printf("\n");
 
    printf("Job Profit: \t");
    for(i=0; i<n; i++){
         printf("%d \t",jobs[i].profit);
    }
    printf("\n");
}

int main()
{
    Job jobs[]=  {{'w', 1, 19}, {'v', 2, 100}, {'x', 2, 27},
                   {'y', 1, 25}, {'z', 3, 15}};
    display(jobs,5);
    //sorting jobs[] w.r.t profit
    qsort(jobs,5,sizeof(jobs[0]),compareJob);
    bestJob(jobs,5);
    return 0;
}

C++

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef struct {
    char id;
    int deadline;
    int profit;
 
}Job;
 
bool compareJob(Job a, Job b){
    //Will return true if a's profit > b's profit
    //else will return false
    return a.profit > b.profit;
}
 
void bestJob(Job jobs[],int sizeOfJobs){
    char jobsToDo[5] {'\0'}; //Assign every element of array to '\0'-Only works in few compilers
    //If above line do not work use for loop to assign '\0' to every element
    int k;
    for(int i=0; i< sizeOfJobs; i++){
            k= jobs[i].deadline-1;
        //Searching for empty date nearest to deadline backwards
        while(jobsToDo[k] != '\0' && k >= 0){
            k--;
        }
        if(k != -1)
            jobsToDo[k]= jobs[i].id;
    }
 
    cout << "Best order and jobs to do is \n";
    k=0;
    while(jobsToDo[k] != '\0'){
            cout << jobsToDo[k] << " ";
            k++;
        }
}
 
void display(Job jobs[],int n){
    int i;
    cout << "Job Id: \t";
    for(i=0; i<n; i++){
        cout << jobs[i].id << "\t";
    }
    cout << endl;
    cout << "Job Deadline: \t";
    for(i=0; i<n; i++){
        cout << jobs[i].deadline << "\t";
    }
    cout << endl;
    cout << "Job Profit: \t";
    for(i=0; i<n; i++){
        cout << jobs[i].profit << "\t";
    }
    cout << endl;
}

int main()
{
    Job jobs[]=  {{'w', 1, 19}, {'v', 2, 100}, {'x', 2, 27},
                   {'y', 1, 25}, {'z', 3, 15}};
    display(jobs,5);
    //sorting jobs[] w.r.t profit
    sort(jobs,jobs+5,compareJob);
    bestJob(jobs,5);
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public 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;
    }
 
    @Override
    public int compareTo( Job b) {
        //Descending order of profit
        return  b.profit - this.profit;
    }
}

public class JobSequencing {
    List<Job> jobs;
 
    public JobSequencing(List<Job> jobs) {
        this.jobs = jobs;
    }
 
    void bestJob() {
        char jobsToDo[] = new char[5];
        int k;
 
        for (Job job : jobs) {
            k = job.deadline - 1;
            //Searching for empty date nearest to deadline backwards
            while ( k >= 0 && jobsToDo[k] != '\0' ) {
                k--;
            }
            if (k != -1)
                jobsToDo[k] = job.id;
        }
 
        System.out.println("Best order and jobs to do is ");
        k = 0;
        while (jobsToDo[k] != '\0') {
            System.out.println(jobsToDo[k] + " ");
            k++;
        }
    }
 
    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();
    }
}

public class App {
    public static void main(String args[]){
        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));
        JobSequencing js = new JobSequencing(jobs);
        js.display();
        //sorting jobs[] w.r.t profit
        Collections.sort(jobs);
        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

fifteen + 5 =