#1235 Maximum Profit in Job Scheduling
the problem
In plain words
Job i runs from startTime[i] to endTime[i] and pays profit[i]. Choose jobs whose time ranges don't overlap and return the highest total pay. A job may begin at the very moment another one finishes.
in startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
out 120
Jobs 1–3 (50) and 3–6 (70).
in startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
out 150
Jobs 1–3, 4–6 and 6–9: 20 + 70 + 60.
in startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
out 6
- 1 ≤ n ≤ 5·10⁴
- 1 ≤ startTime[i] < endTime[i] ≤ 10⁹
- 1 ≤ profit[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DPBinary search (exact & bounds)
where this runsBooking one resource — a single GPU server, a studio, a hall — for the most revenue from paid slots that can't overlap is exactly this problem.
Sort jobs by end time. For job i you either skip it (the best of the first i − 1 jobs) or take it — and then only jobs that end by its start can come before it. Those jobs form a prefix of the sorted list, so a binary search finds where that prefix ends.
solutions
From brute force to optimal
Sort by start; best(i) = max(skip → best(i + 1), take → profit + best(first job starting at or after its end)).
- Sort by start.
- Scan forward for the next compatible job.
- Return the better of skip and take.
Take or skip for every job, nothing cached.
Recursion depth n.
class Solution { 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 jobs[i..] (sorted by start). */ 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 job that starts after i ends return Math.max(best(jobs, i + 1), // skip job i jobs[i][2] + best(jobs, next)); // take it, jump past its overlaps }}Sort by end; for each job, walk back to the last job that ends in time.
- best[0] = 0.
- k = i − 1; while job k − 1 ends after this start: k−−.
- best[i] = max(best[i − 1], profit + best[k]).
The walk back can cover every earlier job: n²/2 ≈ 1.25·10⁹ steps at n = 5·10⁴.
The jobs and the best array.
class Solution { 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[1], b[1])); // by end time int[] best = new int[n + 1]; // best[i]: max profit using only the first i jobs for (int i = 1; i <= n; i++) { int k = i - 1; while (k > 0 && jobs[k - 1][1] > jobs[i - 1][0]) k--; // walk back to the last job that ends in time best[i] = Math.max(best[i - 1], jobs[i - 1][2] + best[k]); } return best[n]; }}Replace the walk back with a binary search over the sorted end times.
- Sort jobs by end.
- k = number of jobs among the first i − 1 that end ≤ start (upper-bound search).
- best[i] = max(best[i − 1], profit + best[k]); return best[n].
The sort, then one O(log n) search per job.
The sorted jobs and best[].
class Solution { 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[1], b[1])); // by END time int[] best = new int[n + 1]; // best[i]: max profit using only the first i jobs (best[0] = 0) for (int i = 1; i <= n; i++) { int[] job = jobs[i - 1]; int k = countEndingBy(jobs, i - 1, job[0]); // jobs 0..k-1 all end by this start best[i] = Math.max(best[i - 1], job[2] + best[k]); // skip it, or take it after those k } return best[n]; } /** How many of jobs[0..hi) end at or before `time`? They are sorted by end, so binary search. */ private int countEndingBy(int[][] jobs, int hi, int time) { int lo = 0; while (lo < hi) { int mid = (lo + hi) >>> 1; if (jobs[mid][1] <= time) lo = mid + 1; // mid fits: the answer is to its right else hi = mid; // mid ends too late } return lo; }}Sort, search, skip or take
Same DP; TreeMap.floorEntry(start) finds the best plan that has finished by this start.
- Sort by end; map = {0 → 0}.
- take = profit + floorEntry(start).value.
- If take beats lastEntry().value, put(end, take).
Sort + one floorEntry and at most one put per job.
The map holds at most n + 1 entries.
class Solution { 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[1], b[1])); // by end time TreeMap<Integer, Integer> best = new TreeMap<>(); // end time -> best profit finished by then best.put(0, 0); for (int[] job : jobs) { int take = job[2] + best.floorEntry(job[0]).getValue(); // best plan that ends by this start if (take > best.lastEntry().getValue()) best.put(job[1], take); // keep values increasing } return best.lastEntry().getValue(); }}in the room
How to say it in the interview
talk track
- Show greedy failing: earliest-end-first collects many cheap short jobs and misses one long, rich job.
- "Sort by end. best[i] = max(skip, profit + best[k]), where k = how many jobs end by this start."
- "The ends are sorted, so k is a binary search → O(n log n)." Mention TreeMap.floorEntry as the Java shortcut.
traps
- Using < instead of <= between an end and a start: jobs that touch are allowed.
- Sorting by start but binary-searching ends (or the other way round): search in the order you sorted.
- Sorting startTime, endTime and profit separately — a job's three values must move together.
what they ask next
Follow-ups
Every job pays the same?
Then it's "most non-overlapping intervals": greedy by earliest end, O(n log n), no DP (Intervals chapter).
Which jobs did you pick?
Walk back from best[n]: if best[i] == best[i − 1] the job was skipped; otherwise it was taken — record it and jump to its k.
before you submit
Edge cases to test
- One job → its profit.
- A job that starts exactly when another ends can follow it.
- One long, rich job beats several short ones — the greedy trap.
- Times up to 10⁹: never build an array indexed by time.
practise next
Similar problems
- #435Non-overlapping IntervalsMediumin Intervals
- #198House RobberMediumin Dynamic Programming
- #35Search Insert PositionEasyin Binary Search