Maximum Profit in Job Scheduling: DP with Binary Search

LeetCode 1235, Maximum Profit in Job Scheduling, gives you three arrays: startTime, endTime, and profit, each of length n. Job i runs from startTime[i] to endTime[i] and earns profit[i]. You need to find the maximum profit you can earn by selecting a subset of non-overlapping jobs. Two jobs overlap if one starts before the other ends.

Why this problem matters

This is the classic weighted interval scheduling problem from algorithm design courses. Unlike basic interval scheduling (where all jobs have equal weight and a greedy approach works), here each job has a different profit. The greedy "pick the earliest ending job" strategy breaks down because a short, low-profit job might block a longer, high-profit one.

Weighted interval scheduling shows up everywhere: allocating meeting rooms for paying clients, scheduling factory production runs, booking freelance contracts, or selecting ad slots. Any time you have competing time-bound tasks with different values, you are solving a variant of this problem.

The key insight

Sort the jobs by end time. Then for each job, you face a binary decision: skip it (carry forward the best profit so far) or take it (add its profit to the best profit you could earn from jobs that end before this one starts). The DP recurrence is:

dp[i] = max(dp[i-1], profit[i] + dp[latest_compatible])

The trick is finding latest_compatible efficiently. Since jobs are sorted by end time, you can binary search for the last job whose end time is <= the current job's start time. That turns an O(n) scan into O(log n) per job, giving you O(n log n) overall.

The solution

from bisect import bisect_right

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(endTime, startTime, profit))
    n = len(jobs)
    ends = [j[0] for j in jobs]
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        end, start, p = jobs[i - 1]
        k = bisect_right(ends, start, 0, i - 1)
        dp[i] = max(dp[i - 1], p + dp[k])

    return dp[n]

The function sorts jobs by end time, then builds a DP array where dp[i] represents the maximum profit considering the first i jobs. For each job, bisect_right finds the insertion point for the current job's start time in the sorted end times. That index k points to the first job that ends after the current job starts, so dp[k] gives the best profit from all compatible earlier jobs.

Visual walkthrough

Notice how the DP values are non-decreasing. That is guaranteed because skipping a job always gives at least dp[i-1]. The final answer lives at dp[n], which accounts for every job's take-or-skip decision.

The binary search at Step 3 is the interesting one. Job 2 starts at time 2, and we need the latest job ending at or before time 2. Job 0 ends at 2, so dp[0] = 40 gets added to job 2's profit of 20, giving 60. That beats skipping (50).

Complexity analysis

Sorting takes O(n log n). The DP loop runs n iterations, each with an O(log n) binary search, giving O(n log n). Space is O(n) for the sorted jobs array and the DP array.

A brute force approach that tries every subset would be O(2^n). A DP without binary search (scanning backwards for the compatible job) runs in O(n^2). The binary search optimization is what brings it down to O(n log n).

The building blocks

1. Weighted interval scheduling DP

dp[i] = max(dp[i - 1], profit[i] + dp[latest_compatible])

This recurrence is the heart of the problem. For each job, you choose the better of two options: skip it and keep the previous best, or take it and add its profit to the best achievable profit from non-overlapping earlier jobs. This pattern applies to any problem where you select a subset of weighted intervals to maximize total value.

2. Binary search for the latest compatible job

k = bisect_right(ends, start, 0, i - 1)

Given a sorted array of end times and a target start time, bisect_right returns the index where start would be inserted to maintain sorted order. All jobs at indices < k end at or before start, making them compatible. This is the standard "find rightmost element <= target" pattern, and it comes up any time you need to efficiently find the boundary between overlapping and non-overlapping ranges.

Edge cases

• Single job. Return its profit. There is nothing to conflict with.
• All jobs overlap. The answer is the maximum individual profit. The DP handles this naturally since each job's "take" option only adds its own profit (no compatible earlier jobs).
• All jobs are non-overlapping. The answer is the sum of all profits. Every "take" option wins.
• Jobs with zero profit. They never improve the total, so the DP skips them automatically.
• Large n (up to 50,000). O(n log n) handles this comfortably. The bottleneck is the sort and n binary searches.
• Jobs with identical time ranges but different profits. Sorting by end time groups them together, and the DP picks the most profitable one.

From understanding to recall

You have seen how sorting by end time, the take-or-skip recurrence, and binary search combine to solve weighted interval scheduling in O(n log n). The logic is clean, but the details matter under pressure: which Python bisect function to use, what range to search, how to index the DP array relative to the sorted jobs.

Spaced repetition locks in those details. You revisit this problem at increasing intervals, each time reconstructing the sort, the recurrence, and the binary search from memory. After a few reps, you see "non-overlapping intervals with weights" and immediately reach for this pattern without hesitation.

Related posts

• Non-overlapping Intervals - The unweighted version where greedy works, a natural stepping stone to this problem
• Merge Intervals - The foundational interval merging pattern, teaching overlap detection
• Minimum Number of Arrows to Burst Balloons - Another greedy interval problem that relies on sorting by end time

The weighted interval scheduling pattern is one of the core DP building blocks that CodeBricks helps you internalize through spaced repetition. Instead of re-deriving the recurrence each time, you drill it until the sort-DP-binary-search pipeline is automatic.