Untitled

 avatar
unknown
plain_text
3 months ago
2.1 kB
2
Indexable
import java.util.ArrayList;
import java.util.Arrays;

class Solution {

    // Job class to represent a job with its id, deadline, and profit
    static class Job {
        int id, deadline, profit;

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

    public ArrayList<Integer> JobSequencing(int[] id, int[] deadline, int[] profit) {
        int n = id.length;

        // Step 1: Create an array of Job objects
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(id[i], deadline[i], profit[i]);
        }

        // Step 2: Sort jobs based on profit in descending order
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

        // Step 3: Find the maximum deadline
        int maxDeadline = 0;
        for (Job job : jobs) {
            maxDeadline = Math.max(maxDeadline, job.deadline);
        }

        // Step 4: Create a hash array (slot availability) initialized with -1
        int[] slots = new int[maxDeadline + 1]; // Slot array 1-indexed
        Arrays.fill(slots, -1);

        // Variables to track the number of jobs done and total profit
        int count = 0;
        int totalProfit = 0;

        // Step 5: Schedule jobs
        for (Job job : jobs) {
            // Try to find a slot for this job from its deadline down to 1
            for (int j = job.deadline; j > 0; j--) {
                if (slots[j] == -1) { // If the slot is free
                    slots[j] = job.id; // Assign the job id to this slot
                    count++; // Increment the count of jobs
                    totalProfit += job.profit; // Add the job's profit
                    break; // Move to the next job
                }
            }
        }

        // Step 6: Return the result
        ArrayList<Integer> result = new ArrayList<>();
        result.add(count); // Number of jobs completed
        result.add(totalProfit); // Total profit
        return result;
    }
}
Editor is loading...
Leave a Comment