Skip to main content

1335. Minimum Difficulty of a Job Schedule

hard

Split a job array into d consecutive non-empty days; each day's difficulty is the max job in that day, and the total is the sum. Partition DP with running-max — clean 2D state, tight monotonic-stack optimization for the O(n * d) form.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You want to schedule a list of jobs in d days. Jobs are dependent (i.e., to work on the ith job, you have to finish all the jobs j where 0 <= j < i). You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day. Given an integer array jobDifficulty and an integer d, return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Constraints

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

Examples

Example 1

Input
jobDifficulty = [6,5,4,3,2,1], d = 2
Output
7

Explanation: Day 1 = [6,5,4,3,2] (max 6), Day 2 = [1] (max 1). Total 7.

Example 2

Input
jobDifficulty = [9,9,9], d = 4
Output
-1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If d > n return -1.

Hint 2

dp[i][k] = min total difficulty to schedule the first i jobs in k days. Last day covers jobs[j..i-1] for some j >= k-1.

Hint 3

Transition: dp[i][k] = min over valid j of dp[j][k-1] + max(jobs[j..i-1]). O(n^2 * d).

Solution approach

Reveal approach

Define the subproblem dp[i][k] = the minimum total difficulty to schedule the first i jobs (indices 0..i-1) into exactly k days. The recurrence relation is dp[i][k] = min over j in [k-1, i-1] of dp[j][k-1] + max(jobDifficulty[j..i-1]) — the last day takes jobs j..i-1 and contributes their max. Base case dp[i][1] = max(jobDifficulty[0..i-1]). Final answer dp[n][d], or -1 if n < d. Implement with two nested loops: outer k from 1 to d, middle i from k to n, inner j scanning backward from i-1 to k-1 while maintaining a running max of jobDifficulty over the suffix. Time O(n^2 * d), space O(n * d). For tighter performance, a monotonic stack reduces the inner loop and yields O(n * d), but the O(n^2 * d) version passes within the n <= 300 constraint and is the version expected in most interviews.

Complexity

Time
O(n^2 * d)
Space
O(n * d)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • partition-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Minimum Difficulty of a Job Schedule and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →