Job Sequencing Problem (Using DSU)

Given a set of n jobs where each job i has a deadline di >=1 and profit pi>=0. Only one job can be scheduled at a time. Each job takes 1 unit of time to complete. We earn the profit if and only if the job is completed by its deadline. The task is to find the subset of jobs that maximizes profit.

Examples:

Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
   a      4      20
   b      1      10
   c      1      40
   d      1      30
Output: Following is maximum profit sequence of jobs:
       c, a

Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
   a     2       100
   b     1       19
   c     2       27
   d     1       25
   e     3       15
Output: Following is maximum profit sequence of jobs:
       c, a, e

A greedy solution of time complexity O(n2) is already discussed here. Below is the simple Greedy Algorithm.

1. Sort all jobs in decreasing order of profit.

2. Initialize the result sequence as first job in sorted jobs.

3. Do following for remaining n-1 jobs

   • If the current job can fit in the current result sequence without missing the deadline, add current job to the result. Else ignore the current job.

The costly operation in the Greedy solution is to assign a free slot for a job. We were traversing each and every slot for a job and assigning the greatest possible time slot(<deadline) which was available.

What does greatest time slot means? Suppose that a job J1 has a deadline of time t = 5. We assign the greatest time slot which is free and less than the deadline i.e 4-5 for this job. Now another job J2 with deadline of 5 comes in, so the time slot allotted will be 3-4 since 4-5 has already been allotted to job J1.

Why to assign greatest time slot(free) to a job? Now we assign the greatest possible time slot since if we assign a time slot even lesser than the available one than there might be some other job which will miss its deadline. Example: J1 with deadline d1 = 5, profit 40 J2 with deadline d2 = 1, profit 20 Suppose that for job J1 we assigned time slot of 0-1. Now job J2 cannot be performed since we will perform Job J1 during that time slot.

Using Disjoint Set for Job Sequencing All time slots are individual sets initially. We first find the maximum deadline of all jobs. Let the max deadline be m. We create m+1 individual sets. If a job is assigned a time slot of t where t => 0, then the job is scheduled during [t-1, t]. So a set with value X represents the time slot [X-1, X]. We need to keep track of the greatest time slot available which can be allotted to a given job having deadline. We use the parent array of Disjoint Set Data structures for this purpose. The root of the tree is always the latest available slot. If for a deadline d, there is no slot available, then root would be 0. Below are detailed steps.

class Solution {
    static class Job {
        char id;
        int deadline, profit;

        public Job(char id, int deadline, int profit) {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
    }

    int parent[];

    public void printJobScheduling(ArrayList<Job> arr) {
        Collections.sort(arr, (a, b) -> b.profit - a.profit);
        // Find max deadline
        int maxDeadline = 0;
        for (Job x : arr)
            maxDeadline = Math.max(maxDeadline, x.deadline);
        // Parent array
        parent = new int[maxDeadline + 1];
        for (int i = 0; i <= n; i++)
            parent[i] = i;
        // Traverse through all the jobs
        for (Job temp : arr) {
            // Find the maximum available free slot for
            // this job (corresponding to its deadline)
            int availableSlot = dsu.find(temp.deadline);

            // If maximum available free slot is greater
            // than 0, then free slot available
            if (availableSlot > 0) {
                // This slot is taken by this job 'temp'
                // so we need to update the greatest free
                // slot. So now we need to merge parents availableSlot-1 & availableSlot
                merge(find(availableSlot - 1), availableSlot);
                System.out.print(temp.id + " ");
            }
        }
    }

    // Path Compression
    int find(int s) {
        if (s == parent[s])
            return s;
        return parent[s] = find(parent[s]);
    }

    void merge(int u, int v) {
        parent[v] = u;
    }
}