DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Job Scheduling Problem with Max Profit

Problem

class Solution {
    // sort on the basis of profit in descending order and try to execute the jobs as close to their deadline as possible
    ArrayList<Integer> JobScheduling(Job jobs[], int n) {
        // Your code here
        Arrays.sort(jobs,(a,b)-> b.profit-a.profit);
        int maxDeadline= -1;
        for(int i=0;i<jobs.length;i++){
            maxDeadline = Math.max(maxDeadline, jobs[i].deadline);
        }
        int slots[]  = new int[maxDeadline];
        Arrays.fill(slots,-1);
        int profit = 0;
        int noOfJobs = 0;
        for(int i =0;i<jobs.length;i++){
            for(int j  = jobs[i].deadline-1;j>=0;j--){
                if(slots[j]==-1) {
                    noOfJobs++;
                    profit+=jobs[i].profit;
                    slots[j] = jobs[i].id;
                    break;
                }
            }
        }

        ArrayList<Integer> list = new ArrayList<>();
        list.add(noOfJobs);
        list.add(profit);
        return list;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)