Maximum Profit in Job Scheduling (LeetCode 1235)

The problem

You get n jobs. Job i runs from startTime[i] to endTime[i] and pays profit[i]. Choose a set of jobs with no two overlapping and return the largest total profit. A job may start at exactly the moment another ends.

Input:  startTime = [1, 2, 3, 3]
        endTime   = [3, 4, 5, 6]
        profit    = [50, 10, 40, 70]
Output: 120

Take the job [1, 3] (50) and the job [3, 6] (70). They touch at time 3, which is allowed.

How to think about it

Start with brute force. Try every subset of jobs and keep the non-overlapping ones: 2ⁿ subsets. With n = 50,000 that’s impossible.

Greedy doesn’t work. “Earliest end first” is right when every job is worth the same (the unweighted version), but with profits, one long well-paid job can beat many short ones. You need DP.

The key insight: sort by end time, then each job either joins or doesn’t. After sorting, let best(t) be the most profit from jobs that finish by time t. For a job (s, e, p), either skip it, or take it and add the best from jobs that finish by s. That “latest job finishing by s” is found with binary search, because end times are sorted.

Keep only improving entries. The code keeps two parallel lists, ends and best, and appends (e, cand) only when cand beats best[-1]. Both lists then stay increasing, so best[i] at the found position is the best profit achievable by time s, and best[-1] is always the answer so far.

Which pattern is this? Weighted interval scheduling: DP over sorted intervals plus binary search. The tell is “non-overlapping intervals, each with a weight, maximise the total”.

Approach

1. Zip into (end, start, profit) and sort, so jobs come in order of end time.
2. Start ends = [0] and best = [0]: by time 0 you’ve earned nothing.
3. For each job (e, s, p):
   1. i = bisect_right(ends, s) - 1: the last recorded end time ≤ s.
   2. cand = best[i] + p: take this job after the best compatible schedule.
   3. If cand > best[-1], append e to ends and cand to best.
4. Return best[-1].

Solution

import bisect
def job_scheduling(startTime, endTime, profit):
    jobs = sorted(zip(endTime, startTime, profit))      # by end time
    ends = [0]; best = [0]
    for e, s, p in jobs:
        i = bisect.bisect_right(ends, s) - 1            # last end <= s (touching is OK)
        cand = best[i] + p                              # take this job
        if cand > best[-1]:                             # keep only improvements
            ends.append(e); best.append(cand)
    return best[-1]
# job_scheduling([1,2,3,3], [3,4,5,6], [50,10,40,70]) -> 120
# job_scheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60]) -> 150

Dry run

Jobs sorted by end time, with the lists after each step:

best[-1] is 120.

Complexity

• Time: O(n log n). Sorting is O(n log n), and each of the n jobs does one O(log n) binary search.
• Space: O(n). For the sorted jobs and the two lists.

Edge cases and pitfalls

• Touching jobs (end == start) are compatible. That’s why it is bisect_right: an end equal to s must be included. bisect_left would wrongly exclude it.
• Sorting by start time makes the “best before this job” lookup much harder. Sort by end.
• Several jobs with the same end time are fine: a worse one is simply not appended.
• Greedy by profit or by earliest end both fail on weighted inputs.
• We cross-checked the code against a brute force over all subsets on 300 random small inputs.

Related problems

• Non-overlapping Intervals (LeetCode 435): the unweighted version, where greedy by end time works.
• Longest Increasing Subsequence (LeetCode 300): another DP sped up by binary search on a sorted helper list.
• Meeting Rooms II (LeetCode 253): intervals sorted by time, different question.