Job Sequencing Problem with C++

Introduction

In this article, we will discuss the job sequencing problem. The job sequencing problem requires us to select jobs in such a way that it maximizes the total profit and deadlines must be taken into consideration.

Problem Statement

You are given a number of jobs and each job has a deadline and profit linked with it. In other words, each job has a specific duration for which we can do that job. Each job takes a single unit of time. Now you need to determine the maximum profit gained if only one job can be scheduled at a time.

Input 1:

ID	Profit	Deadline
A	60	4
B	20	1
C	30	1
D	40	1

Output 1:

The ideal sequence of jobs for the above case is: D -> A and the maximum profit gained is equal to 100.

Input 2:

ID	Profit	Deadline
A	70	4
B	20	1
C	30	2
D	40	1
E	60	3

Output 2:

The ideal sequence of jobs for the above case is: D -> C -> E -> A and the maximum profit gained is equal to 200.

Naive approach

In this section, we will discuss the brute force approach or the naive method to solve the job sequencing problem. The naive method is to produce all the possible subsets of the given jobs and then check then deal with the individual subset for the valid job in that particular subset. During this process also keep the track of the maximum profit among all the valid subsets.

Optimized approach

In this section, we will see the greedy approach for the job sequencing problem which is faster than the naive method. This approach requires you to greedily pick the jobs that can provide us the maximum profit. This also requires us to sort the jobs on the basis of the decreasing order of their profit. This will help us to get the maximum profit as we are choosing the maximum profit for each time slot.

The following is the step by step process of this approach:

The first step is to sort all the jobs on the basis of decreasing the order of profit.
Then, iterate over the jobs in the decreasing order of the profit. Then, for each specific job we need to do the following steps:
Look for a time slot S such that this slot must be empty and it fulfills the condition: S < deadline and S must be as large as possible. Mark this slot with the job and block this slot (since no two jobs can be done at a particular time).
If there exists no such S then we must discard that job.

Code Implementation

Consider the following program that implements this algorithm:

#include <bits/stdc++.h>
using namespace std;

// Structure
typedef struct Job {

char id;
int profit;
int deadline;

} Job;

// Comparator function
bool compare(Job a, Job b)
{
return (a.profit - b.profit);
}

// Get maximum profit from jobs
void jobSequence(Job jobs[], int n)
{
// Sort all jobs as per the decreasing order of the profit
sort(jobs, jobs + n, compare);

int result[n]; // To store result (Sequence of jobs)
bool time[n]; // To keep track of free time

// Initially all time points must be available
for (int i = 0; i < n; i++)
time[i] = false;

// Iterate over time
for (int i = 0; i < n; i++) {

// Find the free time
for (int j = min(n, jobs[i].deadline) - 1; j >= 0; j--) {

// Free slot found
if (time[j] == false) {
result[j] = i;
time[j] = true;
break;
}
}
}

// Print the result
for (int i = 0; i < n; i++)
{
if (time[i])
{
cout << jobs[result[i]].id << ' ';

}
}
}

// Driver's code
int main()
{

// All jobs
Job jobs[] = { { 'A', 70, 4 },
{ 'B', 20, 1 },
{ 'C', 30, 2 },
{ 'D', 40, 1 },
{ 'E', 60, 3 } };
int n = 5;
cout << "The maximum profit can be achieved by doing the following jobs in sequence.\n";

// Calling jobSequence() function
jobSequence(jobs, n);
return 0;
}

write your code here: Coding Playground

Output:

Complexity Analysis

Time complexity - O(N^2)

Space complexity - O(N)

Conclusion

In this tutorial, we discussed the job sequencing problem. We believe this tutorial has been interesting for you.