Pick non-overlapping jobs for the most profit: sort by end time, then each job either skips or adds to the best plan a binary search finds.
▼The problem
LeetCode 1235 (Hard). Job i runs from startTime[i] to endTime[i] and pays profit[i]. Pick jobs with no two overlapping (a job ending at time X is compatible with one starting at X) to make the most total profit.
Examples (LeetCode's): startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] → 120 (jobs 1 and 4; the walkthrough example); startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] → 150 (jobs 1, 4 and 5); startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] → 6 (checked, not shown).
The solution
from bisect import bisect_right
def jobScheduling(startTime, endTime, profit):
jobs = sorted(zip(endTime, startTime, profit))
ends = [e for e, s, p in jobs]
dp = [0] * (len(jobs) + 1)
for i, (e, s, p) in enumerate(jobs, 1):
j = bisect_right(ends, s)
dp[i] = max(dp[i - 1], p + dp[j])
return dp[-1]Transcript
Maximum Profit in Job Scheduling. Each job has a start, end and profit. You can't work two jobs that overlap, but one may start right as another ends. Find the most profit.
One to three pays fifty, two to four pays ten, three to five pays forty, and three to six pays seventy. Take the first and last: one hundred twenty.
The naive way tries every set of jobs that don't clash: two to the n.
Greedy fails too. Taking whatever ends first gets ninety. Grabbing the biggest profit first, in LeetCode's second example, gets one twenty, not one fifty.
Sort the jobs by end time. Let dp of i be the best profit from the first i jobs. Job i is skipped, keeping dp of i minus one, or taken: its profit plus dp of j, where j counts the jobs ending by its start. Keep the larger.
The ends are sorted, so binary search finds j: the last end at or before the start.
In code, sort by end, list the ends, and fill dp left to right. Bisect right gives j. Return the last entry.
Let's walk it. Job one: fifty. Job two starts at two; nothing ends by then, so taking gives ten; skipping keeps fifty. Job three starts at three, as job one ends: forty plus fifty, ninety. Job four: seventy plus fifty, one hundred twenty.
Sorting plus a binary search per job: order n log n time, order n space.
Sort by end, search back, take or skip. That's Maximum Profit in Job Scheduling.