Untitled
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