# Job sequencing with deadlines in C++

In this tutorial, we will see how to solve Job sequencing with deadlines in C++. Initially, we will understand what the problem is and will solve it using the greedy method.

The **Greedy method** is a way to solve problems in which we always choose the next solution as the one which gives us the most obvious solution. In this way, we often neglect the efficient one. The Greedy method always gives us a locally optimal solution. Because it makes us select only the immediate best solution and not the globally one.

## C++ for job sequencing with deadlines

For example, here we are given 5 tasks and when these tasks will be completed we will get a profit. So associated, with these jobs a profit is given. But that task must only be completed in that deadline to gain the profit. We have to identify the sequence of jobs which offer us the maximum profit. Every job takes a single unit of time for its completion.

Now to maximize the entire profit we will think this way. That we need to complete those jobs first which gives us the maximum profit but they must be completed in their deadline. So, it’s a maximization problem. We can solve it using the greedy method.

This is the data given to us:

Jobs J1 J2 J3 J4 J5 Profits 20 15 10 5 1 Deadlines 2 2 1 3 3

Since the maximum deadline is 3. It means that no job is ready to wait beyond 3 hours for its completion. Now, if we apply the greedy method on it. We will arrange the jobs in decreasing profit. Now, let us pick the J1 with profit 20 and deadline 2. Since its deadline is 2 we can schedule it as below.

0------------1-----------------2------------3 J1

The Second highest job is J2. Now go to the 1-2 slot, it can wait till 2 hrs but the slot is already occupied. Now, we will see if any slots are available on the left side and yes it is. So, we assign it the 0-1 slot.

0------------1-----------------2------------3 J2 J1

Now let us select the next job whose deadline is 1. Can we do this job? No, because our slot is already full so it is rejected.

Now the next job has a deadline of 3. So we will do this job. 0------------1-----------------2------------3 J2 J1 J4

Now, for J5 we have no slots available so we will reject it.

That’s it, we have got our solution to the problem.

{J2,J1,J4} or {J1,J2,J4} Total profit will be: 40

### Algorithm for code

1) Sort all the jobs by decreasing order of profit.

2) Initializing the result sequence as the first job in sorted the jobs.

3) Do following for remaining n-1 jobs

a) If the current job can fit in the current slot without missing the deadline, add the current job to the result. Else reject the current job.

### Implementation of the above algorithm with C++: Job sequencing with deadlines

#include<iostream> #include<algorithm> using namespace std; // A structure to represent a job struct Job { char id; int dead; int profit; }; // This function is used for sorting all the jobs according to the profit bool compare(Job a, Job b) { return (a.profit > b.profit); } void jobschedule(Job arr[], int n) { // Sort all jobs according to decreasing order of prfit sort(arr, arr+n, compare); int result[n]; // To store result bool slot[n]; // Initialize all slots to be free for (int i=0; i<n; i++) slot[i] = false; for (int i=0; i<n; i++) { // Find a free slot for this job (Note that we start // from the last possible slot) for (int j=min(n, arr[i].dead)-1; j>=0; j--) { // Free slot found if (slot[j]==false) { result[j] = i; // Add this job to result slot[j] = true; // Make this slot occupied break; } } } // Print the result for (int i=0; i<n; i++) if (slot[i]) cout << arr[result[i]].id << " "; } int main() { Job arr[] = { {'a', 2, 20}, {'b', 2, 15}, {'c', 1, 10}, {'d', 3, 5}, {'e', 3, 1}}; int n = 5; cout << "maximum profit sequence of jobs is-->"; jobschedule(arr, n); }

Output:

maximum profit sequence of jobs is-->b a d

Time complexity: o(n^2)

Also, refer to:

Count the number of occurrences of an element in a linked list in C++

Thank you!

for (int j=min(n, arr[i].dead)-1; j>=0; j–)

What did you mean by the loop ? More specifically, what did you mean by the iteration?

@maruf

By this loop, for(int i=0;i=0; j–)

We are selecting the last possible slot we could find for our job. j is started from 5 for example and it is initially checking the last(fifth) slot of its free, then the fourth and so on …