Coding · Dynamic programming
Maximum Profit in Job Scheduling
- Reported once
- Hard
- campus SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You get n jobs, each with a start time, a later end time and a profit; a set of jobs can be done only if no two overlap, though a job may start exactly when another ends. Return the largest total profit you can collect. For starts [1,2,3,3], ends [3,4,5,6] and profits [50,10,40,70] the answer is 120, from the first and last jobs. There can be 50,000 jobs and times up to a billion, so a table indexed by time is not an option.
Restated in our own words, not a quote from Meesho or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: can a job start at the exact moment another ends, and does that count as overlapping? Is start always smaller than end? Can profits be zero or negative? How many jobs are there, and how large can the times be, since that decides whether a table indexed by time is possible? Are the three arrays the same length? What do I return for no jobs?
I would assume touching jobs are allowed, start is less than end, profits are positive, the three arrays line up by index, and 0 is the answer for an empty list. I would return only the total profit, not the chosen jobs.
Brute force
Say the obvious answer and why it is too slow.
The direct approach is include or exclude: for each job decide to take it or not, keep only the choices with no overlap, and return the best total. That is O(2^n), hopeless beyond about 25 jobs. A better version sorts by end time and fills a table where best[i] looks back through every earlier job to find the compatible ones, which is O(n²).
With 50,000 jobs, n² is over a billion comparisons. Another tempting table, indexed by clock time, needs one cell per time unit, and with times up to a billion that is too much memory and time. The slow part of the O(n²) version is the backward scan, and it can be avoided because the compatible jobs have a special shape.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(2^n), or O(n²) with DP
- Time
- O(n log n)
- Space
- O(n)
The pattern is sort, dynamic programming and binary search, a weighted version of interval scheduling. Sort the jobs by end time. Define best[i] as the largest profit using only the first i jobs in that order. For job i there are two choices. Skip it, and the value is best[i]. Take it, and the value is its profit plus the best result among earlier jobs that end no later than its start. So best[i + 1] is the larger of the two.
Why it is correct: any optimal schedule either leaves job i out, in which case it is an optimal schedule of the first i jobs, or includes it. If it includes job i, every other chosen job must finish by the start of job i, and the best way to choose those is the same problem on a smaller set. The two cases cover every schedule, so taking the larger is exact.
Why binary search works: the jobs are sorted by end time, so the jobs that end by a given moment always form a prefix of the list. The size of that prefix is found by binary search for the first job whose end is later than the start of job i. That turns the backward scan into O(log n). The sort is O(n log n) and so are the n searches, and best takes O(n) space. The plain earliest-finish greedy fails here because profits differ. I would say it as: sorted by end, either skip the job, or take it and add the best that fits before it.
Walk it through
A dry run on the example, step by step.
| Job | (start,end,profit) | j: jobs ending by start | Take: best[j]+profit | Skip | New best |
|---|---|---|---|---|---|
| 1 | (1,3,50) | 0 | 0 + 50 = 50 | 0 | 50 |
| 2 | (2,4,10) | 0 | 0 + 10 = 10 | 50 | 50 |
| 3 | (3,5,40) | 1 | 50 + 40 = 90 | 50 | 90 |
| 4 | (3,6,70) | 1 | 50 + 70 = 120 | 90 | 120 |
Use starts [1,2,3,3], ends [3,4,5,6], profits [50,10,40,70]. The jobs are already sorted by end time, so the trace goes in input order. Job (1,3,50): no job ends by time 1, so j = 0, take gives 50 and skip gives 0, best 50. Job (2,4,10): j is still 0 because the first job ends at 3, after time 2; taking gives only 10, so best stays 50.
Job (3,5,40): the first job ends at 3, which is not later than the start 3, so it fits and j = 1. Take is best[1] + 40 = 90, beating skip at 50. Job (3,6,70): j = 1 again, take is 50 + 70 = 120 against skip at 90. The answer is 120. The trace table lists, for each job, j, the take value, the skip value and the new best.
The code
Runnable JavaScript, checked against test cases.
function jobScheduling(startTime, endTime, profit) {
const jobs = startTime
.map((start, i) => ({ start, end: endTime[i], gain: profit[i] }))
.sort((a, b) => a.end - b.end);
const best = new Array(jobs.length + 1).fill(0);
for (let i = 0; i < jobs.length; i++) {
let lo = 0;
let hi = i;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (jobs[mid].end <= jobs[i].start) lo = mid + 1;
else hi = mid;
}
best[i + 1] = Math.max(best[i], best[lo] + jobs[i].gain);
}
return best[jobs.length];
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No jobs: the loop does not run and best[0] = 0 is returned. One job: its profit. Jobs that touch end to start: the comparison is end less than or equal to start, so they are allowed. All jobs overlapping: every take value is that job's profit plus zero, so the answer is the largest single profit.
Jobs with equal end times: the sort order among them does not matter, because a job that ends at the same time as job i also ends after job i starts, so it never falls inside the prefix we count. The binary search looks only at the first i jobs, never at later ones. The three input arrays are zipped into objects before sorting, so each profit stays with its job. Sums stay far below the largest safe integer in JavaScript at these sizes.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the chosen jobs and not just the total profit?
- What changes if jobs that touch end to start are not allowed?
- How would you solve it if you could pick at most k jobs?
- Why does the plain earliest-finish greedy fail once profits differ?
- How would you handle jobs that arrive one at a time in order of end time?
Where candidates slip
The mistakes this problem punishes.
The classic mistake is sorting only the end times, or sorting the start times separately, so a profit ends up attached to the wrong job. Zip the three arrays first. Another is using strict less than when comparing an end with a start, which refuses jobs that merely touch. People also sort by start time and then run the same DP, which makes the compatible jobs no longer a prefix.
Others: running the binary search over the whole array instead of the first i jobs; returning best[i] without adding the profit of the job that was taken; a greedy by highest profit or earliest finish, both wrong with weights; and the O(n²) DP, which passes small tests and times out on large ones. Also remember that Array sort needs a numeric comparator, since the default sorts numbers as text.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.