The question

Maximum Profit in Job Scheduling

You receive three equally sized arrays: startTime, endTime, and profit. Entry i describes one job. Choose any subset of jobs that do not overlap and return the largest total profit.

Example: jobs [4, 5, 8] and [8, 10, 10] can be taken together for profit 18.

A job ending at time X can be followed by one starting at exactly X.

Watch the schedule unfold

The skip branch descends to the base case. Then recursive calls return in reverse order, caching each take-or-skip answer.

Current jobNext compatible jobBest scheduleOther job

Job · profit

Best profit—

The decision at this job

Sort by start time. solve(i) returns the best profit from job i onward, and memo[i] saves it.

Skip this job—Use the next job’s answer.

Take this job—Add its profit to the next compatible answer.

Recursive call and return

Cached answers by sorted position

Chosen jobs

Step through to reveal the schedule.

Why this works

After sorting by start time, every schedule from job i either skips it or takes it. If we take it, a binary search finds the first job whose start time is at least this job’s end time. That includes jobs that begin at the exact moment it ends.

solve(i) = max(solve(i + 1), profit[i] + solve(next[i]))

Calling solve(0) follows skip calls down to solve(n) = 0. As calls return, each result is stored in memo; later calls reuse that value. Sorting and binary searches take O(n log n) time. Memoization uses O(n) space, plus the recursion stack.

Example 1’s answer is 18 from original jobs 3 and 4.

Python interview solution

Explicit recursion and memoization, with a binary search for the next compatible job.

import sys

def jobScheduling(startTime, endTime, profit):
    jobs = []
    for i in range(len(startTime)):
        jobs.append((startTime[i], endTime[i], profit[i]))
    jobs.sort()

    starts = []
    for job in jobs:
        starts.append(job[0])

    n = len(jobs)
    sys.setrecursionlimit(n + 1000)
    memo = [None] * n

    def solve(i):
        if i == n:
            return 0
        if memo[i] is not None:
            return memo[i]

        left = i + 1
        right = n
        while left < right:
            mid = (left + right) // 2
            if starts[mid] < jobs[i][1]:
                left = mid + 1
            else:
                right = mid

        skip = solve(i + 1)
        take = jobs[i][2] + solve(left)
        memo[i] = max(skip, take)
        return memo[i]

    return solve(0)