Job Sequencing Problem

Given a set of n jobs where each job_i has a deadline and profit associated with it.

Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with a job if and only if the job is completed by its deadline.

Find the number of jobs done and the maximum profit.

Note: Jobs will be given in the form (Job_id, Deadline, Profit) associated with that Job. Deadline of the job is the time on or before which job needs to be completed to earn the profit.

Examples :

Input: N = 4, Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output: 2 60
Explanation: Job1 and Job3 can be done with maximum profit of 60 (20+40).

Input: N = 5, Jobs = {(1,2,100),(2,1,19),(3,2,27),(4,1,25),(5,1,15)}
Output: 2 127
Explanation: 2 jobs can be done with maximum profit of 127 (100+27).

Expected Time Complexity: O(nlogn)
Expected Auxilliary Space: O(n)

Constraints:
1 <= n <= 10⁵
1 <= Deadline,id <= n
1 <= Profit <= 500

Approach 01:

#include <vector>
#include <algorithm>
#include <utility> // For std::pair

using namespace std;

class Solution {
public:
    // Function to find the maximum profit and the number of jobs done.
    vector<int> JobScheduling(Job jobs[], int n) {
        int maxDeadline = 0;

        // Find the maximum deadline across all jobs
        for (int i = 0; i < n; ++i) {
            maxDeadline = max(maxDeadline, jobs[i].dead);
        }

        // Convert array to vector for easier sorting
        vector<Job> jobList(jobs, jobs + n);

        // Sort jobs in descending order of profit
        sort(jobList.begin(), jobList.end(), [](const Job& a, const Job& b) {
            return a.profit > b.profit;
        });

        // Initialize the count of jobs done and total profit
        int jobCount = 0;
        int totalProfit = 0;

        // Array to keep track of filled slots (initialized to -1, meaning empty)
        vector<int> slotAvailability(maxDeadline + 1, -1);

        // Iterate over the jobs to schedule them
        for (const auto& job : jobList) {
            // Try to find a slot for the current job, starting from its deadline
            for (int slot = job.dead; slot > 0; --slot) {
                if (slotAvailability[slot] == -1) {  // Slot is available
                    totalProfit += job.profit;  // Add job's profit
                    slotAvailability[slot] = 1;  // Mark slot as filled
                    jobCount++;  // Increment the job count
                    break;  // Move to the next job
                }
            }
        }

        // Return the number of jobs done and total profit
        return {jobCount, totalProfit};
    }
};

from typing import List

class Solution:
    #Function to find the maximum profit and the number of jobs done.
    def JobScheduling(self,Jobs,n):
        
        deadline = 0
        
        for each in Jobs:
            deadline = max(deadline,each.deadline)
        Jobs.sort(key = lambda x:x.profit,reverse=True)
        length = len(Jobs)
        count =0
        profit = 0
        dead = [-1]*(deadline+1)
        for i in range(length):
            for j in range(Jobs[i].deadline,0,-1):
                if dead[j]==-1:
                    profit = profit+Jobs[i].profit
                    dead[j]=1
                    count+=1
                    break
            
        return (count,profit)

Time Complexity

• Finding Maximum Deadline:

  This step involves iterating through all jobs to find the maximum deadline. It takes \( O(n) \) time.

• Sorting Jobs:

  Sorting the jobs based on profit in descending order uses a comparison-based sorting algorithm, which has a time complexity of \( O(n \log n) \).

• Scheduling Jobs:

  For each job, the algorithm tries to find an available slot starting from the job’s deadline and moving backwards. In the worst case, each job might check all slots from its deadline to 1. This operation can be considered \( O(n \times d) \), where \( d \) is the maximum deadline. However, since \( d \) is at most \( n \), this step can be simplified to \( O(n^2) \).

• Overall Time Complexity:

  The most time-consuming step is the job scheduling part, which is \( O(n^2) \). Sorting jobs is \( O(n \log n) \), which is less than \( O(n^2) \). Therefore, the overall time complexity is \( O(n^2) \).

Space Complexity

• Space for Slot Availability:

  The `slotAvailability` vector has a size of \( \text{maxDeadline} + 1 \). In the worst case, this is \( O(n) \) space.

• Space for Job List:

  Storing the jobs in a vector requires \( O(n) \) space.

• Overall Space Complexity:

  The space complexity is dominated by the `slotAvailability` vector and the job list, both of which are \( O(n) \). Therefore, the overall space complexity is \( O(n) \).