Job Sequencing
The job sequencing problem involves scheduling jobs with deadlines and profits to maximize profit, where each job takes unit time and can be done at most once. Greedy: sort jobs by profit descending, and schedule each job at the latest available slot before its deadline.
Java implementation:
static class Job { int deadline, profit; }
public static int jobSequencing(Job[] jobs, int t) {
Arrays.sort(jobs, (a,b) -> b.profit - a.profit);
boolean[] slot = new boolean[t];
int totalProfit = 0;
for (Job job : jobs) {
for (int i = Math.min(t-1, job.deadline-1); i >= 0; i--) {
if (!slot[i]) {
slot[i] = true;
totalProfit += job.profit;
break;
}
}
}
return totalProfit;
}
Time: O(n²) if slots are checked linearly; can be optimized with DSU to O(n log n).
Two Minute Drill
- Job sequencing maximizes profit with unit-time jobs and deadlines.
- Greedy: sort by profit, schedule at latest available slot.
- Time O(n²) naive; O(n log n) with disjoint set.
- Classic scheduling problem.
Need more clarification?
Drop us an email at career@quipoinfotech.com