Hard

Maximum Profit in Job Scheduling

095

Given startTime, endTime, and profit arrays, return the maximum profit from non-overlapping jobs.

EXAMPLES

Example 1

Input
{
  "startTime": [
    1,
    2,
    3,
    3
  ],
  "endTime": [
    3,
    4,
    5,
    6
  ],
  "profit": [
    50,
    10,
    40,
    70
  ]
}

Output
120

FUNCTION SHAPE

startTime: intArrayendTime: intArrayprofit: intArray→int

SOLUTION NOTE

Sort by start time. For each job, either take it (add profit, skip to next non-overlapping job via binary search) or skip it.

Reveal reference solution +

pythonREFERENCE

def jobScheduling(self, startTime: List[int], endTime: List[int],
                          profit: List[int]) -> int:
    jobs = sorted(zip(startTime, endTime, profit))

    @cache
    def dp(i):
        if i >= len(jobs): return 0
        # Binary search for next job we can take
        start, end, p = jobs[i]
        next_idx = bisect_left(jobs, (end,), key=lambda x: x[0])
        # Take this job or skip it
        return max(p + dp(next_idx), dp(i + 1))

    return dp(0)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗