Job Sequencing Problem

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 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.

Your Task :
You don't need to read input or print anything. Your task is to complete the function JobScheduling() which takes an integer N and an array of Jobs(Job id, Deadline, Profit) as input and returns the count of jobs and maximum profit.

Solution Approach

1. Sort all jobs in decreasing order of profit.
2. Iterate on jobs in decreasing order of profit.For each job , do the following :
   • Find a time slot i, such that slot is empty and i < deadline and i is greatest.Put the job in this slot and mark this slot filled.
   • If no such i exists, then ignore the job.

Expected Time complexity: $O(nlogn)$

Click - to see solution code

C++

class Solution {
   public:
    vector<int> JobScheduling(Job arr[], int n) {
        sort(arr, arr + n,
             [](auto& a, auto& b) { return (a.profit > b.profit); });
        int slot = 0;
        for (int i = 0; i < n; i++) {
            slot = max(arr[i].dead, slot);
        }
        int res = 0;
        int count = 0;
        vector<int> v(slot + 1, 0);
        for (int i = 0; i < n; i++) {
            int j = arr[i].dead;
            while (j >= 1 && v[j] != 0) {
                j--;
            }
            if (j >= 1 && v[j] == 0) {
                res += arr[i].profit;
                count++;
                v[j] = 1;
            }
        }
        return {count, res};
    }
};