Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling is a classic "weighted interval scheduling" problem. You cannot run two overlapping jobs, and each job pays differently — so greedily grabbing the highest payout fails. The fix is dynamic programming, with binary search to skip past the jobs you cannot keep.

The slow way first

The brute force is to try every subset of jobs, keep the non-overlapping ones, and take the best total. That is O(2^n) — hopeless for more than a handful of jobs.

A greedy attempt (always take the job that ends soonest, or the one that pays most) also fails: in the example, the highest-paying single job is [4,6] p=70, but the best combination mixes a cheaper early job with later ones. We need to weigh "take this job and lose everything it overlaps" against "skip it." That is a textbook DP setup.

The idea: sort by end, then DP with binary search

Sort the jobs by end time. Define dp[i] = the best profit using only the first i jobs. For each job, we have two choices:

• Skip it → profit stays dp[i-1].
• Take it → earn its profit, then add the best profit from jobs that finish at or before this job starts. Because the list is sorted by end time, that earlier dp value is found with a binary search for the last job ending <= start.

dp[i] = max(dp[i-1], profit + dp[last job ending <= start]).

Because every job only depends on jobs that ended earlier, processing them in end-time order means the answer we need is already computed.

Walk through it

Step through the animation. The pointer i moves across the jobs (already sorted by end time). At each job we binary-search backward for the last compatible job, read its dp, and compare take vs skip. The dp array fills in underneath; its final entry is the answer, 180.

Pseudocode

sort jobs by end time
dp_end = [0]                 # end times we have processed (for binary search)
dp     = [0]                 # dp[0] = best profit with zero jobs = 0
for each job (start s, end e, profit p) in sorted order:
    i = index of last job whose end <= s     # binary search
    take = p + dp[i]
    skip = dp[last]
    append max(skip, take) to dp
    append e to dp_end
return dp[last]

The Python solution

def job_scheduling(start, end, profit):
    jobs = sorted(zip(end, start, profit))
    dp_end = [0]            # sorted end times, dp[0] handles "no job"
    dp = [0]               # dp[i] = best profit using first i jobs
    for e, s, p in jobs:
        i = bisect_right(dp_end, s)   # last job ending <= s
        take = p + dp[i]
        dp.append(max(dp[-1], take))
        dp_end.append(e)
    return dp[-1]

• sorted(zip(end, start, profit)) orders jobs by end time (the first tuple element).
• dp_end mirrors the dp array: dp_end[i] is the end time of the i-th processed job, kept sorted so we can binary-search it.
• bisect_right(dp_end, s) finds how many jobs end at or before this job starts — that index i points at the best compatible dp value.
• take = p + dp[i] is this job's profit plus the best we could earn before it started.
• dp.append(max(dp[-1], take)) records the better of skipping (carry dp[-1]) and taking.
• dp[-1] at the end is the best profit over all jobs.

Complexity

The dominant cost is the sort plus one binary search per job, both O(n log n). The dp and dp_end arrays use O(n) extra space.

When this pattern shows up

Practice