Schedule Unit Jobs Before Their Deadlines for Maximum Profit
Solve this ProblemYou have several jobs, each taking exactly one unit of time and each with a deadline and a profit. Only one job can run in any time unit (units are numbered 1, 2, 3, …), and a job earns its profit only if it runs in some unit up to its deadline. Jobs may be skipped. Find the maximum total profit.
Checking every subset of jobs for feasibility works but grows exponentially. The greedy approach considers jobs from most to least profitable and drops each one into the latest still-free time unit at or before its deadline, skipping it if none is free.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ deadlines.length ≤ 12, and profits.length equals deadlines.length - ◆
1 ≤ deadlines[i] ≤ 15 and 1 ≤ profits[i] ≤ 100 - ◆
Every job takes exactly one time unit, and only one job can run in each time unit (units are numbered 1, 2, 3, …) - ◆
Job i earns profits[i] only if it runs in a time unit from 1 up to deadlines[i]; a job may also be skipped. Return the maximum total profit
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Subset of Jobs for a Valid Schedule
BruteFor every subset of jobs (a bitmask), decide whether all of them can meet their deadlines. A set of unit jobs is schedulable exactly when, after sorting the deadlines in increasing order, the k-th job (counting from 1) has a deadline of at least k — the k-th earliest deadline needs room for k jobs before it. Sum the profit of every schedulable subset and keep the largest. It is correct because it looks at every possibility, but there are 2ⁿ subsets.
O(2ⁿ · n log n)O(n)1class Solution {
2 public int maxJobProfit(int[] deadlines, int[] profits) {
3 int n = deadlines.length;
4 int best = 0;
5 for (int mask = 1; mask < (1 << n); mask++) {
6 List<Integer> chosen = new ArrayList<>();
7 int profit = 0;
8 for (int i = 0; i < n; i++) {
9 if ((mask & (1 << i)) != 0) {
10 chosen.add(deadlines[i]);
11 profit += profits[i];
12 }
13 }
14 Collections.sort(chosen);
15 boolean feasible = true;
16 for (int k = 0; k < chosen.size(); k++) {
17 if (chosen.get(k) < k + 1) { feasible = false; break; }
18 }
19 if (feasible) best = Math.max(best, profit);
20 }
21 return best;
22 }
23}Optimal — Most Profitable First, Into the Latest Free Slot
OptimalConsider jobs from most to least profitable. A job is worth doing if some time unit up to its deadline is still free; to keep the earlier units open for other jobs, put it in the LATEST free unit at or before its deadline (search downward from the deadline; deadlines beyond n can be capped at n since at most n jobs ever run). If a free unit is found, mark it used and bank the profit; otherwise skip the job — every unit before its deadline is already occupied by a job that is at least as profitable. D is the largest deadline considered.
O(n log n + n · D)O(n)1class Solution {
2 public int maxJobProfit(int[] deadlines, int[] profits) {
3 int n = deadlines.length;
4 Integer[] order = new Integer[n];
5 for (int i = 0; i < n; i++) order[i] = i;
6 Arrays.sort(order, (a, b) -> profits[b] - profits[a]);
7 boolean[] taken = new boolean[n + 1];
8 int total = 0;
9 for (int idx : order) {
10 for (int slot = Math.min(deadlines[idx], n); slot >= 1; slot--) {
11 if (!taken[slot]) {
12 taken[slot] = true;
13 total += profits[idx];
14 break;
15 }
16 }
17 }
18 return total;
19 }
20}