Job Sequencing with Deadline in O(nlogn) complexity

Published in

CodingWithYash

5 min readSep 4, 2020

Problem Statement:

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

Solution:

Given an array

arr = [(5, 100), (1, 19), (2, 27), (1, 25), (3, 30), (3, 28)]

Here each array element is a pair of values, where the first value is the deadline of the job and the second value is the profit assign to it.

Now let's just create a function jobSequenceDeadline and it will gonna take only one argument i.e. the array variable only.

def jobSequenceDeadline(arr):
  # entire logic

Now I am going to solve this step by step so that it will become easy to understand.

Step 1: Sort the array in descending order of its profit.

Each element of the array represents the job and each job contains a deadline and its profit.

So the array we have is a tuple of two values and we need to sort it in descending order of its profit.

def sortPara(val):
  return val[1]arr.sort(key = sortPara, reverse = True)

Sorting will take O(nlogn)

Now the array will look like this

arr = [(5, 100), (3, 30), (3, 28), (2, 27), (1, 25), (1, 19)]

Step 2: Find the max deadline among all the given deadline and also create an array of size n + 1 and give the initial value zero it, where n is the max deadline

maxDeadline = max(arr)[0]
job = [0 for i in range(maxDeadline + 1)]

This operation will take O(n)

Step 3: Next create a dictionary or hash map and count the occurrences of all the deadline

In the given array, the occurrence of deadline 5 is 1, the occurrence of deadline 3 is 2, the occurrence of deadline 2 is 1, and the occurrence of deadline 1 is 2.

deadlines = {}
for i in range(0, len(arr)):
  if arr[i][0] in deadlines:
    deadlines[arr[i][0]] += 1
  else:
    deadlines[arr[i][0]] = 1

This will also take O(n)

NOTE: the in operator is O(1) for dictionaries and sets in python

Step 4: Check the missing deadline and handle it accordingly

This step may look complex and will try to make it easy

So in the given array, we have a job with deadlines 1, 2, 3, 5 and we do no have deadline 4.

Now understand, the maximum number of jobs that we can able to do is equal to the maximum deadline we have.

In this particular case, the maximum deadline we have is 5, so the maximum number of jobs we can able to do is 5.

But actually, with the given array it is not possible to do 5 jobs here we are able to do only 4 jobs.

Now let's just try to understand when we can do the maximum number of jobs and when not.

When we have all the deadlines then of course we are able to do the maximum number of jobs.
If we miss any deadline then the jobs with higher than the missing deadline occur at least more than once.

In this particular case, we miss deadline 4, and the number of jobs with a higher deadline than 4 is only 1 and to do the maximum number of jobs we need at least more than 1.

So is this case we are not able to do the maximum number of jobs.

req = []
for key in range(1, maxDeadline + 1):
  if key not in deadlines:
    req.append(key)
  elif deadlines[key] > 1 and len(req) > 0:
    req.pop()

This function will find the missing deadline due to which we are not able to perform the maximum number of jobs.

In this case, we get

req = [4]

This operation will also take O(n)

NOTE: the in operator is O(1) for dictionaries and sets in python

Step 5: Let just find the maximum number of jobs possible

So the maximum number of jobs that are possible is the difference between the maximum deadline and length of the req array.

Here, the maximum deadline represents the maximum number of jobs possible, and the length of the req array represents the number of possibilities that are not possible because we do not have any processes to fill the deadlines available in req array.

total_possible_job = maxDeadline - len(req)

Step 6: Final step — let's just find the jobs that are possible

So, let's just understand the logic used here to find the jobs in such a way that the total profit will be maximum.

So, we have already sort the array in descending order according to its profit.

Now, here we understand the role of the job array that we have created earlier.

count = 0
ans = []for i in range(len(arr)):
  if count >= total_possible_job:
    break
  elif job[arr[i][0]] < arr[i][0]:
    count += 1
    job[arr[i][0]] += 1
    ans.append(arr[i])

Here we basically doing this:

job[1] < 1 -> job[1] can have one jobjob[2] < 2 -> job[2] can have two jobjob[3] < 3 -> job[3] can have three jobjob[4] < 4 -> job[4] can have four jobjob[5] < 5 -> job[5] can have five job

And when the count becomes equal to total_possible_job we will break the loop and return the ans array.

ans = [(5, 100), (3, 30), (3, 28), (2, 27)]