Job Sequencing With Deadlines

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:

Input

Output: J4 J3 J1 J2
Explanation:

Output

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:

Dry Run

Sort in decreasing order of profits:

Sort in decreasing order
sequence of jobs

C++Implementation

struct Job
{
   char id;     
   int dead;  
   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;
    int deadline, profit;
  
    public Job() {}
  
    public Job(char id, int deadline, int profit)
    {
        this.id = id;
        this.deadline = deadline;
        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][2] < arr[j + 1][2]:
                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, -1):
            if result[j] is False:
                result[j] = True
                job[j] = arr[i][0]
                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[1] > job2[1];
}
 
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++)
    {
        maxDeadline = max(maxDeadline, jobs[i][0]);
    }
    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][0] < *slots.rbegin())
        {
            continue;
        }
 
        int availableSlot = *slots.lower_bound(jobs[i][0]);
        maxProfit = maxProfit + jobs[i][1];
        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[1] < second[1]) return 1;
            else return -1;
        }
        });
 
        int maxProfit = 0;
        int maxDeadline = 0;
        for (int i = 0; i < jobs.length; i++)
        {
            maxDeadline = Math.max(maxDeadline, jobs[i][0]);
        }
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = maxDeadline; i > 0; i--)
        {
            set.add(i);
        }
        TreeSet<Integer> slots = (TreeSet<Integer>)set.descendingSet();
 
        for (int i = 0; i < jobs.length; i++)
        {
            if (slots.size() == 0 || jobs[i][0] < slots.last())
            {
                continue;
            }
 
            Integer availableSlot = -1;
 
            for (Integer val : slots)
        {
                if (val <= jobs[i][0])
                {
                    availableSlot = val;
                    break;
                }
            }
 
            if (availableSlot != -1)
            {
                maxProfit = maxProfit + jobs[i][1];
 
                slots.remove(availableSlot);
            }
        }
 
        return maxProfit;
    }

PythonImplementation of Approach

import bisect
 
def jobScheduling(jobs):
 
    jobs.sort(key = lambda x: (-x[1], -x[0]))
    maxProfit = 0
    maxDeadline = 0
 
    for i in range(0, len(jobs)):
        maxDeadline = max(maxDeadline, jobs[i][0])
 
    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][0] < slots[0]:
            continue
 
        availableSlot = slots[bisect.bisect(slots, jobs[i][0]) - 1]
        maxProfit += jobs[i][1]
        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
Permutations of the Given String

Permutation Of String

Next Post
Minimum Number of Jumps

Minimum Number of Jumps

Total
0
Share