Job Sequencing

Practice Link

You are given three arrays: id, deadline, and profit, where each job is associated with an ID, a deadline, and a profit. Each job takes 1 unit of time to complete, and only one job can be scheduled at a time. You will earn the profit associated with a job only if it is completed by its deadline.

Your task is to find:

The maximum number of jobs that can be completed within their deadlines. The total maximum profit earned by completing those jobs.

Greedy Approach#

• Intuition: To maximize profit, process jobs in descending order of profit — always try to schedule the highest-paying job first. Each job just needs any free slot at or before its deadline; choosing the latest available slot preserves earlier slots for jobs with tighter deadlines.
• Mechanics: Sort jobs by profit descending. Maintain a slots array of size maxDeadline+1 initialised to -1. For each job, scan backwards from deadline to 1 and assign it to the first empty slot found. If no slot is available, the job is skipped.
• Trade-off: Sorting is O(n log n); the inner scan over slots makes the worst case O(n × m) where m is the maximum deadline. When m is large this becomes a bottleneck — the DSU variant below brings the inner operation to near-O(1) amortized.

We need to maximize the profit -> pick jobs with higer profits -> Sort based on profits

• create an array slots, size = maxDeadline given.
• start picking jobs with maxProfit and filling slots.
• Now if for a job with deadline x, slot is already filled -> check for all slots 0 -> x-1

class Job {
    public:
    int id;
    int deadline;
    int profit;
};

class Solution {
  public:
    static bool cmp(Job a, Job b)
    {
        return a.profit > b.profit;
    }
  
    vector<int> JobSequencing(vector<int> &id, vector<int> &deadline,
                              vector<int> &profit) {
        int n = id.size();
        vector<Job> jobs;
        for(int i=0;i<n;i++)
        {
            Job j;
            j.id = id[i];
            j.deadline = deadline[i];
            j.profit = profit[i];
            jobs.push_back(j);
        }
        
        sort(jobs.begin(), jobs.end(), cmp);
        
        
        int maxDeadline = *max_element(deadline.begin(), deadline.end());
        vector<int> slots(maxDeadline+1,-1);
        
        int jobsCompleted=0, profitEarned=0;
        for(int i=0;i<n;i++)
        {
            for(int j=jobs[i].deadline;j>0;j--)
            {
                if(slots[j] == -1)
                {
                    slots[j] = j;
                    jobsCompleted++;
                    profitEarned += jobs[i].profit;
                    break;
                }
            }
            
        }
        return {jobsCompleted,profitEarned};
    }
};

Time Complexity: O(nlogn) + O(mn), where m->maxDeadline

Space Complexity: O(m)

optimized Greedy with DSU#

• Intuition: The bottleneck of the basic greedy is the inner backward scan to find the latest free slot. Disjoint Set Union (DSU) can answer "what is the latest free slot at or before position x?" in near-O(1) amortized time by maintaining a parent array where each occupied slot points to the next free slot below it.
• Mechanics: Initialise parent[i] = i for all slots (every slot is its own representative — it is free). When a slot s is assigned, union it with s-1: parent[s] = findAvailableSlot(parent, s-1). Subsequent calls to findAvailableSlot(parent, x) will path-compress and jump directly to the next available slot, skipping occupied ones.
• Trade-off: The DSU find with path compression runs in O(α(m)) amortized time (effectively constant), reducing the overall complexity from O(n × m) to O(n log n) dominated by the sort. Ideal for large inputs where m (maxDeadline) is big.

class Job {
    public:
    int id;
    int deadline;
    int profit;
};

class Solution {
  public:
    static bool cmp(Job a, Job b)
    {
        return a.profit > b.profit;
    }
    
    int findAvailableSlot(vector<int> &parent, int slot) {
        if (parent[slot] == slot) return slot;
        return parent[slot] = findAvailableSlot(parent, parent[slot]);
    }
  
    vector<int> JobSequencing(vector<int> &id, vector<int> &deadline,
                              vector<int> &profit) {
        int n = id.size();
        vector<Job> jobs(n);
        for(int i=0;i<n;i++)
        {
            jobs[i] = {id[i], deadline[i], profit[i]};
        }
        
        sort(jobs.begin(), jobs.end(), cmp);
        
        
        int maxDeadline = *max_element(deadline.begin(), deadline.end());
        vector<int> slots(maxDeadline+1);
        for (int i = 0; i <= maxDeadline; i++) slots[i] = i;
        
        int jobsCompleted=0, profitEarned=0;
        for(int i=0;i<n;i++)
        {
            int availableSlot = findAvailableSlot(slots, min(maxDeadline, jobs[i].deadline));
            if (availableSlot > 0) {
                slots[availableSlot] = findAvailableSlot(slots, availableSlot - 1); 
                jobsCompleted++;
                profitEarned += jobs[i].profit;
            }
            
        }
        return {jobsCompleted,profitEarned};
    }
};

Time Complexity: O(nlogn), better performing for large n

Space Complexity: O(m)

Dp Approach#

• Recursive DP with Memoization avoids redundant computations.
• Efficient for small N, but greedy methods are preferred for larger cases.
• Since constraints are large, we will avoid using this approach