Java - Job Sequencing Problem
Problem Statement
You are given N jobs, where each job has a deadline and a profit associated with it. The goal is to schedule jobs in such a way that maximum profit is obtained, while ensuring that each job is completed before its deadline. Each job takes only one unit of time to complete.
Example
mathematica
Input: jobs = [{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}]
Each job is represented as {JobID, Deadline, Profit}.
Output: {2, 60}
Explanation:
- Job 3 (Profit 40) → Slot 1
- Job 4 (Profit 30) → Cannot be scheduled
- Job 1 (Profit 20) → Slot 2
- Job 2 (Profit 10) → Cannot be scheduled
Total jobs done = 2, Total profit = 60
Approach
Sort jobs in descending order of profit.
Find the latest available slot for each job before its deadline.
Use an array to track occupied time slots.
Java Code
import java.util.Arrays;
import java.util.Comparator;
class Job {
int id, deadline, profit;
public Job(int id, int deadline, int profit) {
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
}
public class JobSequencing {
public static int[] jobScheduling(Job[] jobs) {
// Sort jobs by profit in descending order
Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
// Find the maximum deadline
int maxDeadline = 0;
for (Job job : jobs) {
maxDeadline = Math.max(maxDeadline, job.deadline);
}
// Create a slot array initialized to -1 (indicating free slots)
int[] slots = new int[maxDeadline + 1];
Arrays.fill(slots, -1);
int totalProfit = 0, jobCount = 0;
for (Job job : jobs) {
// Find a free slot from the job's deadline moving backwards
for (int i = job.deadline; i > 0; i--) {
if (slots[i] == -1) { // If the slot is free
slots[i] = job.id;
totalProfit += job.profit;
jobCount++;
break;
}
}
}
return new int[]{jobCount, totalProfit};
}
public static void main(String[] args) {
Job[] jobs = {
new Job(1, 4, 20),
new Job(2, 1, 10),
new Job(3, 1, 40),
new Job(4, 1, 30)
};
int[] result = jobScheduling(jobs);
System.out.println("Max jobs: " + result[0] + ", Max profit: " + result[1]);
}
}
Complexity Analysis
Sorting Jobs: O(N log N)
Finding Slots: O(N * D) (D = max deadline)
Overall Complexity: O(N log N + N * D), which is efficient for reasonable constraints.
Example Walkthrough
Input
jobs = [{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}]
Sorted Jobs by Profit
Job 3 → Profit 40, Deadline 1
Job 4 → Profit 30, Deadline 1
Job 1 → Profit 20, Deadline 4
Job 2 → Profit 10, Deadline 1
Scheduling
Slot 1 → Job 3 (Profit 40)
Slot 2 → Job 1 (Profit 20)
Output
Max jobs: 2, Max profit: 60
