Job Sequencing Problem

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

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

public class Solution {
    static class Job {
        char id; // Job Id
        int dead; // Deadline of job
        int profit; // Profit if job is over before or on deadline
    };

    public int[] printJobScheduling(Job arr[], int n) {
        Arrays.sort(arr, (a, b) -> b.profit - a.profit);

        int result[] = new int[n];
        boolean slot[] = new boolean[n];

        for (int i = 0; i < n; i++) {
            for (int j = Math.min(n, arr[i].dead) - 1; j >= 0; j--) {
                // Free slot found
                if (slot[j] == false) {
                    result[j] = i; // Add this job to result
                    slot[j] = true; // Make this slot occupied
                    break;
                }
            }
        }
        return result;
    }
}
// DSU
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;
    }
}