What is the main approach to solve Maximum Profit in Job Scheduling?

Use state transition dynamic programming with jobs sorted by end time and binary search to find the latest non-overlapping job for each step.

Can jobs that end and start at the same time be scheduled together?

Yes, a job ending at time X allows inclusion of another job starting at X without overlapping.

What is the time complexity for this DP with binary search approach?

Sorting takes O(n log n) and each job uses O(log n) binary search, resulting in O(n log n) overall time complexity.

How does GhostInterview help with edge cases?

It guides users to check DP updates for overlapping jobs and ensures correct maximum profit calculations on examples.

Are there common mistakes to avoid in this problem?

Yes, forgetting inclusive end-start scheduling, not using binary search, or miscalculating DP states are frequent errors.

#1235

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

规划兼职工作

你打算利用空闲时间来做兼职工作赚些零花钱。这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i] 。给你一份兼职工作表，包含开始时间 startTime ，结束时间 endTime 和预计报酬 profit 三个数组，请你…

数组二分查找动态规划排序

题目描述

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

示例 1：

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：
我们选出第 1 份和第 4 份工作， 
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。

示例 2：

输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出：150
解释：
我们选择第 1，4，5 份工作。 
共获得报酬 150 = 20 + 70 + 60。

示例 3：

输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输出：6

提示：

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

lightbulb

解题思路

方法一：记忆化搜索 + 二分查找

我们先将工作按照开始时间从小到大排序，然后设计一个函数 $dfs(i)$ 表示从第 $i$ 份工作开始，可以获得的最大报酬。答案即为 $dfs(0)$ 。

函数 $dfs(i)$ 的计算过程如下：

对于第 $i$ 份工作，我们可以选择做，也可以选择不做。如果不做，最大报酬就是 $dfs(i + 1)$ ；如果做，我们可以通过二分查找，找到在第 $i$ 份工作结束时间之后开始的第一份工作，记为 $j$ ，那么最大报酬就是 $profit[i] + dfs(j)$ 。取两者的较大值即可。即：

dfs(i)=\max(dfs(i+1),profit[i]+dfs(j))

其中 $j$ 是满足 $startTime[j] \ge endTime[i]$ 的最小的下标。

此过程中，我们可以使用记忆化搜索，将每个状态的答案保存下来，避免重复计算。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 是工作的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        @cache
        def dfs(i):
            if i >= n:
                return 0
            _, e, p = jobs[i]
            j = bisect_left(jobs, e, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), p + dfs(j))

        jobs = sorted(zip(startTime, endTime, profit))
        n = len(profit)
        return dfs(0)

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to sorting and binary search for each job. Space complexity is O(n) for storing DP states and the combined job list.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect sorting by end times before DP.
question_mark
Look for correct DP state definition to store maximum profit up to each job.
question_mark
Binary search for previous compatible job is crucial for efficiency.

warning

常见陷阱

外企场景

error
Forgetting that a job ending at X can allow a new job starting at X.
error
Performing linear search instead of binary search, increasing runtime.
error
Incorrectly updating DP array, not considering the maximum between including or skipping a job.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow jobs with equal start and end times and handle them in DP updates.
arrow_right_alt
Find the maximum number of jobs instead of profit using a similar DP approach.
arrow_right_alt
Add a constraint on maximum total duration and adapt the DP to track both profit and duration.

help

常见问题

外企场景

继续练习

#1187 使数组严格递增 #792 匹配子序列的单词数 #2008 出租车的最大盈利