#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/amazon-interview-prep/amazon-coding-iv-dp-design/leetcode-1235-maximum-profit-in-job-scheduling-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/amazon-interview-prep/amazon-coding-iv-dp-design/leetcode-1235-maximum-profit-in-job-scheduling-implementation

Repovive

LeetCode 1235 Maximum Profit in Job Scheduling - Implementation - Amazon Coding IV: DP & Design | Amazon Interview Prep | Repovive

Repovive.

Amazon Interview Prep9 sections · 182 units9h total

Open in Course

LeetCode 1235 Maximum Profit in Job Scheduling - Implementation

The approach

After sorting by end time, binary search finds where to connect each job's profit to the DP table. I'll walk through the pseudocode.

function jobScheduling(startTime, endTime, profit):
    n = length(startTime)
    jobs = []
    for i from 0 to n-1:
        jobs.append((endTime[i], startTime[i], profit[i]))
    sort jobs by endTime

    dp = array of size n+1, filled with 0
    ends = [job.endTime for job in jobs]

    for i from 1 to n:
        // Option 1: skip this job
        dp[i] = dp[i-1]

        // Option 2: take this job
        // find latest job ending <= jobs[i-1].startTime
        lo = 0
        hi = i - 1
        idx = 0
        while lo <= hi:
            mid = (lo + hi) / 2
            if ends[mid] <= jobs[i-1].startTime:
                idx = mid + 1
                lo = mid + 1
            else:
                hi = mid - 1

        dp[i] = max(dp[i], jobs[i-1].profit + dp[idx])

    return dp[n]