How do I minimize the job schedule difficulty?

You can minimize the job schedule difficulty by dividing the jobs into `d` days, using dynamic programming to compute the optimal splits and minimize the difficulty of each schedule.

Why does dynamic programming work for this problem?

Dynamic programming works because we can break down the problem into subproblems of calculating the minimum difficulty for each split, building the solution progressively.

What happens if `d` is greater than the number of jobs?

If `d` is greater than the number of jobs, it is impossible to schedule all jobs, as each day must have at least one job, and the function will return -1.

How does state transition help with solving this problem?

State transition allows us to track the minimal difficulty across different splits of the job array, ensuring that we calculate the least possible difficulty as we divide the jobs into `d` days.

What is the time complexity of this problem?

The time complexity is typically O(n * d^2), where `n` is the number of jobs and `d` is the number of days, due to the DP approach iterating through all possible splits.

#1335

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

工作计划的最低难度

你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 ）。你每天至少需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。给你一个整数数组 jobDifficulty 和一个整数…

数组动态规划

题目描述

你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。

你每天至少需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。

给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。

返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

示例 1：

输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7

示例 2：

输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。

示例 3：

输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3 。

示例 4：

输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15

示例 5：

输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843

提示：

1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示完成前 $i$ 项工作，且一共用了 $j$ 天的最小难度。初始时 $f[0][0] = 0$ ，其余 $f[i][j]$ 均为 $\infty$ 。

考虑第 $j$ 天的工作安排，我们可以枚举第 $j$ 天完成的工作 $[k,..i]$ ，那么有状态转移方程：

f[i][j] = \min_{k \in [1,i]} \{f[k-1][j-1] + \max_{k \leq t \leq i} \{jobDifficulty[t-1]\}\}

最终答案即为 $f[n][d]$ 。

时间复杂度 $O(n^2 \times d)$ ，空间复杂度 $O(n \times d)$ 。其中 $n$ 和 $d$ 分别为工作数量和需要计划的天数。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        f = [[inf] * (d + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(d + 1, i + 1)):
                mx = 0
                for k in range(i, 0, -1):
                    mx = max(mx, jobDifficulty[k - 1])
                    f[i][j] = min(f[i][j], f[k - 1][j - 1] + mx)
        return -1 if f[n][d] >= inf else f[n][d]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests for edge cases where `d` is greater than the number of jobs.
question_mark
Challenges in efficiently computing the minimum difficulty when dividing the jobs into groups.
question_mark
The ability to understand and implement dynamic programming with state transitions in job scheduling.

warning

常见陷阱

外企场景

error
Overcomplicating the solution by not efficiently handling the DP state transitions.
error
Forgetting to handle the base case where `d` is greater than the number of jobs.
error
Not updating the DP table correctly while iterating through possible splits, leading to incorrect difficulty calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Varying the size of the job array, potentially increasing complexity with larger inputs.
arrow_right_alt
Changing the number of days `d`, which requires adjusting the approach for splitting the job array.
arrow_right_alt
Allowing different job difficulties to test how the algorithm handles varied input distributions.

help

常见问题

外企场景

继续练习

#1340 跳跃游戏 V #1326 灌溉花园的最少水龙头数目 #1349 参加考试的最大学生数