Maximum Profit in Job Scheduling
Problem
n jobs; job i occupies the time interval
[startTime[i], endTime[i]) and pays profit[i]. Choose a set of jobs
whose intervals do not overlap and return the largest total profit. A job that
ends at time x is compatible with a job that starts at x.start = [1,2,3,3], end = [3,4,5,6], profit = [50,10,40,70]Output120 (jobs 1 and 4)start = [1,2,3,4,6], end = [3,5,10,6,9], profit = [20,20,100,70,60]Output150start = [1,1,1], end = [2,3,4], profit = [5,6,4]Output61 ≤ n ≤ 5 × 104 · 1 ≤ start[i] < end[i] ≤ 109 · 1 ≤ profit[i] ≤ 104
Try it yourself
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
}
}
i jobs
either skips job i or takes it plus the best profit of all jobs that finish
by its start — and that prefix length is found by binary search on the sorted
end times.Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.
Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.
Open the Grid DP guide →Approaches
Brute ForceTake-or-Skip Recursion
O(n · 2n)Space O(n)Sort by start time and decide job by job. Skipping moves to the next job; taking it earns its profit and jumps to the first later job that starts no earlier than its end (found by a linear scan). Every compatible subset is explored.
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n = startTime.length; int[][] jobs = new int[n][]; for (int i = 0; i < n; i++) jobs[i] = new int[] {startTime[i], endTime[i], profit[i]}; Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0])); // by start time return best(jobs, 0); } // Best profit using only jobs[i..n-1] private int best(int[][] jobs, int i) { if (i == jobs.length) return 0; int next = i + 1; while (next < jobs.length && jobs[next][0] < jobs[i][1]) next++; // first compatible int take = jobs[i][2] + best(jobs, next); int skip = best(jobs, i + 1); return Math.max(take, skip); }
Simple to reason about, but the subset tree is exponential.
BetterMemoized Recursion (Linear Next Lookup)
O(n2)Space O(n)The result of best(i) depends only on i, so cache it.
There are n states, but each still scans linearly for the next
compatible job, giving O(n2) overall.
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n = startTime.length; int[][] jobs = new int[n][]; for (int i = 0; i < n; i++) jobs[i] = new int[] {startTime[i], endTime[i], profit[i]}; Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0])); int[] memo = new int[n]; Arrays.fill(memo, -1); return best(jobs, 0, memo); } private int best(int[][] jobs, int i, int[] memo) { if (i == jobs.length) return 0; if (memo[i] != -1) return memo[i]; int next = i + 1; while (next < jobs.length && jobs[next][0] < jobs[i][1]) next++; memo[i] = Math.max(jobs[i][2] + best(jobs, next, memo), best(jobs, i + 1, memo)); return memo[i]; }
Polynomial, but the quadratic scan times out at n = 5 × 104.
OptimalSort by End + DP + Binary Search
O(n log n)Space O(n)With jobs ordered by end time, dp[i] = best profit from the first
i jobs. Taking job i allows exactly the jobs whose end is
≤ its start, which form a prefix of the sorted order; binary search finds its
length k, so dp[i] = max(dp[i-1], dp[k] + profit).
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n = startTime.length; Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> Integer.compare(endTime[a], endTime[b])); int[] ends = new int[n]; for (int i = 0; i < n; i++) ends[i] = endTime[order[i]]; int[] dp = new int[n + 1]; // dp[i] = best profit using the first i jobs for (int i = 1; i <= n; i++) { int job = order[i - 1]; int k = countEndingBy(ends, i - 1, startTime[job]); dp[i] = Math.max(dp[i - 1], dp[k] + profit[job]); } return dp[n]; } // How many of ends[0..hi) are <= t (ends is sorted ascending) private int countEndingBy(int[] ends, int hi, int t) { int lo = 0; while (lo < hi) { int mid = (lo + hi) >>> 1; if (ends[mid] <= t) lo = mid + 1; else hi = mid; } return lo; }
Dry runstart = [1,2,3,3], end = [3,4,5,6], profit = [50,10,40,70]
- init0····ends = [3,4,5,6]
- job[1,3)0k50i···k=0: 0+50
- job[2,4)0k5050i··max(50, 0+10)
- job[3,5)050k5090i·k=1: 50+40
- job[3,6)050k5090120ik=1: 50+70 = 120 ✔
Sorting plus one binary search per job — comfortably fast for the limits.
≤ in the binary search: a job ending exactly when another starts
is allowed — the classic off-by-one in this problem.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Take-or-Skip Recursion | O(n · 2n) | O(n) |
| Better | Memoized Recursion (Linear Next Lookup) | O(n2) | O(n) |
| Optimal | Sort by End + DP + Binary Search | O(n log n) | O(n) |
- Treating touching intervals (
end == start) as overlapping. - Sorting the three arrays separately — job attributes must move together (sort indices or tuples).
- Greedy “earliest finish” only maximises the count of jobs, not the profit.
- Name it as weighted interval scheduling: take-or-skip plus “latest compatible job”.
- Explain why the compatible jobs form a prefix once sorted by end time.
- A TreeMap of end → best profit (
floorEntry) is an equally valid O(n log n) variant.