# Job Sequencing With Deadlines

## Problem Statement

Given an array of jobs having a specific deadline and associated with a profit, provided the job is completed within the given deadline. The task is to maximize the profit by arranging the jobs in a schedule, such that only one job can be done at a time.

Examples:
Input:

Output: J4 J3 J1 J2
Explanation:

Total profit – 20 + 25 + 35 + 30 = 110

## Approach 1: Greedy Algorithm

Since, the task is to get the maximum profit by scheduling the jobs, the idea is to approach this problem greedily.

Algorithm

• Sort the jobs based on decreasing order of profit.
• Iterate through the jobs and perform the following:
• Choose a Slot i if:
• Slot i isn’t previously selected.
• I < deadline
• I is maximum
• If no such slot exists, ignore the job and continue.

## Dry Run with Example

Given Jobs:

Sort in decreasing order of profits:

### C++Implementation

```struct Job
{
char id;
int profit;
};
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
void printJobScheduling(Job arr[], int n)
{
sort(arr, arr+n, comparison);

int result[n];
bool slot[n];
for (int i=0; i<n; i++)
slot[i] = false;

for (int i=0; i<n; i++)
{
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
if (slot[j]==false)
{
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}```

### JavaImplementation

```class Job
{
char id;

public Job() {}

public Job(char id, int deadline, int profit)
{
this.id = id;
this.profit = profit;
}
void printJobScheduling(ArrayList<Job> arr, int t)
{
int n = arr.size();
Collections.sort(arr,
(a, b) -> b.profit - a.profit);

boolean result[] = new boolean[t];
char job[] = new char[t];
for (int i = 0; i < n; i++)
{
for (int j
= Math.min(t - 1, arr.get(i).deadline - 1);
j >= 0; j--) {
if (result[j] == false)
{
result[j] = true;
job[j] = arr.get(i).id;
break;
}
}
}
for (char jb : job)
{
System.out.print(jb + " ");
}
System.out.println();
}```

### PythonImplementation

```def printJobScheduling(arr, t):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j] < arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

result = [False] * t
job = ['-1'] * t
for i in range(len(arr)):
for j in range(min(t - 1, arr[i] - 1), -1, -1):
if result[j] is False:
result[j] = True
job[j] = arr[i]
break

print(job)```

Time Complexity: O(N^2), where N is the size of the jobs array
Space Complexity: O(1), since no extra space is used.

## Efficient Approach: Using Set

In the previous approach, for each job, we had to iterate through all other jobs and find a job satisfying the given conditions. But the time complexity is O(N^2) in the worst case. It can be improved further using sets.

The idea is to apply binary search on the set and find the jobs satisfying the given conditions

Algorithm:

• Sort the jobs based on decreasing order of profit.
• Create two variables, total_jobs = 0, maxprofit = 0.
• Also, find the maximum deadline among all the jobs.
• Initialise a set storing all the jobs in decreasing order.
• Iterate through the jobs and perform the following:
• If the set is empty or the deadline of the current job is less than the last element of the set, ignore the job.
• Else, apply binary search and find the nearest Slot i, such that i < deadline and add the profit.
• Increment total jobs by 1 and remove the ith element from the set.
• Return the maximum profit.

### C++Implementation of Approach

```bool compare(vector<int> &job1, vector<int> &job2)
{
return job1 > job2;
}

int jobScheduling(vector<vector<int>> &jobs)
{

sort(jobs.begin(), jobs.end(), compare);

int maxProfit = 0;
int maxDeadline = 0;
for (int i = 0; i < jobs.size(); i++)
{
}
set<int, greater<int>> slots;
for (int i = maxDeadline; i > 0; i--)
{
slots.insert(i);
}

for (int i = 0; i < jobs.size(); i++)
{
if (slots.size() == 0 || jobs[i] < *slots.rbegin())
{
continue;
}

int availableSlot = *slots.lower_bound(jobs[i]);
maxProfit = maxProfit + jobs[i];
slots.erase(availableSlot);
}

return maxProfit;
}```

### JavaImplementation of Approach

```public static int jobScheduling(int[][] jobs)
{
Arrays.sort(jobs, new Comparator<int[]>(){
public int compare(int[] first, int[] second)
{
if(first < second) return 1;
else return -1;
}
});

int maxProfit = 0;
int maxDeadline = 0;
for (int i = 0; i < jobs.length; i++)
{
}
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = maxDeadline; i > 0; i--)
{
}
TreeSet<Integer> slots = (TreeSet<Integer>)set.descendingSet();

for (int i = 0; i < jobs.length; i++)
{
if (slots.size() == 0 || jobs[i] < slots.last())
{
continue;
}

Integer availableSlot = -1;

for (Integer val : slots)
{
if (val <= jobs[i])
{
availableSlot = val;
break;
}
}

if (availableSlot != -1)
{
maxProfit = maxProfit + jobs[i];

slots.remove(availableSlot);
}
}

return maxProfit;
}```

### PythonImplementation of Approach

```import bisect

def jobScheduling(jobs):

jobs.sort(key = lambda x: (-x, -x))
maxProfit = 0

for i in range(0, len(jobs)):

slots = list()

for i in range(1, maxDeadline + 1):
slots.append(i)

maxProfit = 0
for i in range(len(jobs)):

if len(slots) == 0 or jobs[i] < slots:
continue

availableSlot = slots[bisect.bisect(slots, jobs[i]) - 1]
maxProfit += jobs[i]
slots.remove(availableSlot)

return maxProfit```

Time Complexity: O(NlogN), where N is the size of the jobs array
Space Complexity: O(max(deadline)), since set is used.

## FAQs

Q. Do we need to sort the jobs array?
Yes, we need to sort the jobs array according to profit. Else, all the possible subsets need to be found, which would lead to an exponential solution.

Q. What is the most efficient algorithm to solve the Job Sequencing problem?
The job sequencing problem can be solved using the binary search approach using sets. The idea is to find the job corresponding to an ith job whose deadline is less than the current job. This leads to an O(NlogN) approach.

##### Previous Post ## Permutation Of String

##### Next Post 