Job sequencing Problem

Greedy Algorithms Scheduling and Interval Problems Medium

This type of problem is commonly encountered in project management and scheduling software applications
For instance, software that manages tasks and deadlines in industries such as manufacturing, supply chain, or software development often needs to optimise schedules based on profit and deadlines
This involves choosing an order to execute jobs in a way that maximises profit while respecting deadlines — a real-world application of the job scheduling problem

Given an 2D array Jobs of size Nx3, where Jobs[i][0] represents JobID , Jobs[i][1] represents Deadline , Jobs[i][2] represents Profit associated with that job. Each Job takes 1 unit of time to complete and only one job can be scheduled at a time.

The profit associated with a job is earned only if it is completed by its deadline. Find the number of jobs and maximum profit.

Examples:

Input : Jobs = [ [1, 4, 20] , [2, 1, 10] , [3, 1, 40] , [4, 1, 30] ]

Output : 2 60

Explanation : Job with JobID 3 can be performed at time t=1 giving a profit of 40.

Job with JobID 1 can be performed at time t=2 giving a profit of 20.

No more jobs can be scheduled, So total Profit = 40 + 20 => 60.

Total number of jobs completed are two, JobID 1, JobID 3.

So answer is 2 60.

Input : Jobs = [ [1, 2, 100] , [2, 1, 19] , [3, 2, 27] , [4, 1, 25] , [5, 1, 15] ]

Output : 2 127

Explanation : Job with JobID 1 can be performed at time time t=1 giving a profit of 100.

Job with JobID 3 can be performed at time t=2 giving a profit of 27.

No more jobs can be scheduled, So total Profit = 100 + 27 => 127.

Total number of jobs completed are two, JobID 1, JobID 3.

So answer is 2 127.

Input : Jobs = [ [1, 1, 100] , [2, 2, 200] , [3, 3, 300] , [4, 4, 400] ]

Constraints

1 <= N <= 10⁵
1 <= Deadline <= N
1 <= Profit <= 500

Hints

Maintain a timeline (e.g., a list of size equal to the maximum deadline) to keep track of which time slots are occupied. For each job, attempt to schedule it at the latest available time slot before its deadline. If no such slot exists, skip the job.
Keep a count of the number of successfully scheduled jobs. Add the profit of each scheduled job to the total profit. At the end, return the number of jobs and the maximum profit.

Company Tags

Micron Technology Roblox Bloomberg Instacart Morgan Stanley Square Alibaba Airbnb AMD Roche PayPal Siemens Healthineers Western Digital Robinhood Seagate Technology McKinsey & Company Johnson & Johnson eBay GE Healthcare Deloitte Goldman Sachs Zomato Freshworks Riot Games Unity Technologies Google Microsoft Amazon Meta Apple Netflix Adobe

Intuition

The strategy to maximize profit involves prioritizing jobs that offer higher profits. To achieve this, the jobs should be sorted in descending order of profit. For example, a job with a deadline of 4 can be completed anytime between day 1 and day 4. However, performing the job on its last possible day is more beneficial. This leaves earlier days available for other jobs, optimizing the schedule and allowing more jobs to be completed within their deadlines.

Approach

Sort the jobs in descending order of profit.
Determine the maximum deadline and create an array of that size. Initially, set each array index to -1 to indicate no jobs have been scheduled.
For each job, check if it can be performed on its latest possible day.

If possible, mark that index with the job id and add the profit to the total profit.
If not possible, check the previous days until an empty slot is found.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    // Function to calculate maximum profit
    vector<int> JobScheduling(vector<vector<int>>& Jobs) {
        // Sort jobs based on profit in descending order
        sort(Jobs.begin(), Jobs.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] > b[2];
        });

        // Total number of jobs
        int n = Jobs.size();

        /*Initialize a hash table 
        to store selected jobs.
        each element represents a 
        deadline slot, 
        initially unoccupied.*/
        vector<int> hash(n, -1);

        // Initialize count
        int cnt = 0;

        // Initialize the total profit earned
        int totalProfit = 0;

        // Iterate over each job
        for (int i = 0; i < n; i++) {
            /*Iterate over each deadline slot starting 
            from the job's deadline*/
            for (int j = Jobs[i][1] - 1; j >= 0; j--) {
                /*If the current deadline 
                slot is available 
                (not occupied)*/
                if (hash[j] == -1) {
                    // Count of selected jobs
                    cnt++;
                    // Mark the job as selected
                    hash[j] = Jobs[i][0];
                    // Update the total profit
                    totalProfit += Jobs[i][2];
                    // Move to the next job
                    break;
                }
            }
        }

        // Return the vector
        return {cnt,totalProfit};
    }
};

int main() {
    vector<vector<int>> jobs = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
    
    Solution solution;
    vector<int> result = solution.JobScheduling(jobs);
    
    // Output the result
    cout << "Number of Jobs: " << result[1] << endl;
    cout << "Maximum Profit: " << result[0] << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to calculate maximum profit
    public int[] JobScheduling(int[][] Jobs) {
        // Sort jobs based on profit in descending order
        Arrays.sort(Jobs, (a, b) -> b[2] - a[2]);

        // Total number of jobs
        int n = Jobs.length;

        /*Initialize a hash table 
        to store selected jobs.
        each element represents a 
        deadline slot, 
        initially unoccupied.*/
        int[] hash = new int[n];
        Arrays.fill(hash, -1);

        // Initialize count
        int cnt = 0;

        // Initialize the total profit earned
        int totalProfit = 0;

        // Iterate over each job
        for (int i = 0; i < n; i++) {
            /*Iterate over each deadline slot starting 
            from the job's deadline*/
            for (int j = Jobs[i][1] - 1; j >= 0; j--) {
                /*If the current deadline 
                slot is available 
                (not occupied)*/
                if (hash[j] == -1) {
                    // Count of selected jobs
                    cnt++;
                    // Mark the job as selected
                    hash[j] = Jobs[i][0];
                    // Update the total profit
                    totalProfit += Jobs[i][2];
                    // Move to the next job
                    break;
                }
            }
        }

        // Return the array
        return new int[]{cnt,totalProfit};
    }

    public static void main(String[] args) {
        int[][] jobs = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
        
        Solution solution = new Solution();
        int[] result = solution.JobScheduling(jobs);
        
        // Output the result
        System.out.println("Number of Jobs: " + result[1]);
        System.out.println("Maximum Profit: " + result[0]);
    }
}
class Solution:
    # Function to calculate maximum profit
    def JobScheduling(self, Jobs):
        # Sort jobs based on profit in descending order
        Jobs.sort(key=lambda x: x[2], reverse=True)

        # Total number of jobs
        n = len(Jobs)

        """Initialize a hash table 
        to store selected jobs.
        each element represents a 
        deadline slot, 
        initially unoccupied."""
        hash = [-1] * n

        # Initialize count
        cnt = 0

        # Initialize the total profit earned
        totalProfit = 0

        # Iterate over each job
        for i in range(n):
            """Iterate over each deadline slot starting 
            from the job's deadline"""
            for j in range(Jobs[i][1] - 1, -1, -1):
                """If the current deadline 
                slot is available 
                (not occupied)"""
                if hash[j] == -1:
                    # Count of selected jobs
                    cnt += 1
                    # Mark the job as selected
                    hash[j] = Jobs[i][0]
                    # Update the total profit
                    totalProfit += Jobs[i][2]
                    # Move to the next job
                    break

        # Return the list
        return [cnt,totalProfit]

if __name__ == "__main__":
    jobs = [[1, 4, 20], [2, 1, 10], [3, 1, 40], [4, 1, 30]]
    
    solution = Solution()
    result = solution.JobScheduling(jobs)
    
    # Output the result
    print("Number of Jobs:", result[1])
    print("Maximum Profit:", result[0])
class Solution {
    // Function to calculate maximum profit
    JobScheduling(Jobs) {
        // Sort jobs based on profit in descending order
        Jobs.sort((a, b) => b[2] - a[2]);

        // Total number of jobs
        const n = Jobs.length;

        /*Initialize a hash table 
        to store selected jobs.
        each element represents a 
        deadline slot, 
        initially unoccupied.*/
        const hash = Array(n).fill(-1);

        // Initialize count
        let cnt = 0;

        // Initialize the total profit earned
        let totalProfit = 0;

        // Iterate over each job
        for (let i = 0; i < n; i++) {
            /*Iterate over each deadline slot starting 
            from the job's deadline*/
            for (let j = Jobs[i][1] - 1; j >= 0; j--) {
                /*If the current deadline 
                slot is available 
                (not occupied)*/
                if (hash[j] === -1) {
                    // Count of selected jobs
                    cnt++;
                    // Mark the job as selected
                    hash[j] = Jobs[i][0];
                    // Update the total profit
                    totalProfit += Jobs[i][2];
                    // Move to the next job
                    break;
                }
            }
        }

        // Return the array
        return [cnt,totalProfit];
    }
}

// Example usage
const jobs = [[1, 4, 20], [2, 1, 10], [3, 1, 40], [4, 1, 30]];

const solution = new Solution();
const result = solution.JobScheduling(jobs);

// Output the result
console.log("Number of Jobs: " + result[1]);
console.log("Maximum Profit: " + result[0]);

Complexity Analysis

Time Complexity: O(N logN + N²) where N is the number of jobs. First, the jobs are sorted based on profit in descending order, resulting in O(N logN) complexity. Then, the algorithm iterates over the jobs to select them. The outer loop runs once for each job (N iterations), and the inner loop iterates up to the job’s deadline, which can be at most N in the worst case, giving a complexity of O(N²). Space Complexity: O(N) where N is the number of jobs. An array of size N is used to keep track of occupied slots taking O(N) space.

Code

Problem List