1235. Maximum Profit in Job Scheduling

1235

HardIntervals and Sweep LineSort by end, DP with binary search for the last compatible jobWeighted interval scheduling

Maximum Profit in Job Scheduling

Given jobs described by startTime[i], endTime[i], and profit[i], select a subset of non-overlapping jobs maximizing total profit. Two jobs are compatible if one ends at or before the other starts (a job ending at time t and another starting at t may both be taken). Return the maximum profit.

Open official problem prompt ↗

In plain English

Pick a set of time-disjoint jobs that earns the most money, where longer or later jobs may or may not be worth skipping cheaper earlier ones.

Picture it like this

A freelancer with one desk choosing gigs from a calendar. Each accepted gig blocks its time slot. For any gig you consider, you ask: what is the most I could have earned from gigs that were already finished by the time this one starts, plus this gig's pay?

Example

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Why: Take job 0 (1->3, 50) and job 3 (3->6, 70); they do not overlap and sum to 120.

Constraints

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^41 <= startTime[i] < endTime[i] <= 10^91 <= profit[i] <= 10^4

Pattern lesson

See the pattern, then code

Weighted interval scheduling

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Sort jobs by end time. Let dp be the best profit achievable using jobs seen so far. For each job you either skip it (keep dp) or take it: its profit plus the best dp achievable from jobs that finished at or before this job's start, found by binary search.

New words, made simpleKnow these before the algorithm

Weighted interval scheduling: Interval selection where each interval carries a value and total value is maximized
Compatible jobs: Non-overlapping jobs; the next may start exactly when a prior one ends
Binary search for predecessor: Finding the latest-ending job that finishes at or before a given start

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Greedy by profit or by end

Incorrect: unlike the unweighted case, a fat-profit long job can beat several small ones, so greedy misses optima.

Repeatedly take the highest-profit or earliest-ending compatible job.

Time O(n log n)Space O(n)

Best choiceSort by end + DP + binary search

Correct and efficient; the standard weighted-interval-scheduling solution.

dp over jobs ordered by end; for each, combine its profit with the best dp among jobs ending by its start.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

After processing k jobs (sorted by end), dp[k] holds the maximum profit obtainable using any compatible subset drawn from those first k jobs.

Why this is correct

Reasoning

Sorting by end means when we consider a job, every earlier-listed job ends no later, so binary search over the ends array pinpoints the best profit achievable before this job starts. The optimal solution for the first k jobs either excludes job k (value dp[k-1]) or includes it (its profit plus the optimum among jobs ending by its start). Taking the max of these two exhausts the cases, so dp is correct by induction.

The algorithm in three movesSay these aloud before coding

1Zip and sort jobs by end time

dp=[0,50] after job (3,1,50)

2Maintain a parallel ends array and dp array, both seeded with a sentinel 0

job (6,3,70): last end<=3 is index 1 -> dp[1]=50

3For each job, binary-search the last end <= this start to get the best compatible prior profit

50+70=120 -> dp last = 120

4Append max(previous best, that profit + this job's profit)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

(3,1,50)0

(4,2,10)1

(5,3,40)2

(6,3,70)3

1 · Readzip(end,start,profit)

2 · AskOrder by end

3 · Update state(3,1,50),(4,2,10),(5,3,40),(6,3,70)

4 · Resultends=[0], dp=[0]

Key takeaway

Jobs sorted by end; taking (1->3) then (3->6) chains via binary search to 120.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5Sort by end
Zipping with endTime first makes tuple sort order the jobs by finish time.
2
Lines 6-7Seed arrays
A sentinel end 0 and dp 0 represent taking no jobs, so binary search always has a valid target.
3
Lines 9Find predecessor
bisect_right(ends, start) - 1 gives the index of the last job that ends at or before this job's start.
4
Lines 10-12Take or skip
dp[i] + gain is the profit if we take this job; compare with dp[-1] (skip) and append the better one.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single job returns its own profit
All jobs mutually overlapping means only the most profitable one is chosen
Jobs touching at a boundary (one ends when the next starts) are compatible
Widely spaced disjoint jobs are all taken

Common beginner mistakes

Using bisect_left instead of bisect_right, which excludes a job that ends exactly at the current start even though they are compatible
Applying a greedy strategy and missing that a high-profit long job can beat several short ones
Sorting by start rather than end, breaking the binary-search-for-predecessor invariant

Check your understanding

Why must bisect_right be used on the ends array with the job's start, rather than bisect_left?

Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line