1335. Minimum Difficulty of a Job Schedule - Explanation

1. Dynamic Programming (Top-Down)

Intuition

We need to split n jobs across d days, where each day must have at least one job, and the difficulty of a day is the maximum difficulty among all jobs scheduled that day. This is a classic partitioning problem. At each step, we decide how many consecutive jobs to assign to the current day, then recursively solve for the remaining jobs and days. We track the maximum job difficulty seen so far for the current day and explore two choices: extend the current day by including the next job, or end the current day and start a new one.

Algorithm

If there are fewer jobs than days, return -1 (impossible to schedule).
Use memoization with state (i, d, cur_max) where i is the current job index, d is the number of remaining days, and cur_max is the maximum difficulty for the current day so far.
Base case: if i == n, return 0 if d == 0, otherwise infinity (invalid).
At each job i:
- Update cur_max with the current job's difficulty.
- Option 1: include the next job in the current day (continue without decrementing d).
- Option 2: end the current day by adding cur_max and start a new day with the next job.
Return the minimum of both options.

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = {}

        def dfs(i, d, cur_max):
            if i == n:
                return 0 if d == 0 else float("inf")
            if d == 0:
                return float("inf")
            if (i, d, cur_max) in dp:
                return dp[(i, d, cur_max)]

            cur_max = max(cur_max, jobDifficulty[i])
            res = min(
                dfs(i + 1, d, cur_max),
                cur_max + dfs(i + 1, d - 1, -1)
            )
            dp[(i, d, cur_max)] = res
            return res

        return dfs(0, d, -1)

Time & Space Complexity

Time complexity: $O(n * d * m)$
Space complexity: $O(n * d * m)$

Where $n$ is the number of jobs, $d$ is the number of days, and $m$ is the maximum difficulty value among all the job difficulties.

2. Dynamic Programming (Top-Down Optimized)

Intuition

The previous approach tracks cur_max as part of the state, which can lead to many states. We can optimize by restructuring: instead of tracking the current maximum, we iterate over all possible ending positions for the current day. For each starting position i and remaining days d, we try ending the day at positions i, i+1, ..., n-d (leaving enough jobs for remaining days). While iterating, we maintain a running maximum and take the best choice.

Algorithm

If there are fewer jobs than days, return -1.
Define dfs(i, d) as the minimum difficulty to schedule jobs from index i onward over d days.
Base case: if d == 1, return the maximum difficulty among all remaining jobs.
For each possible split point j from i+1 to n-1:
- Track the running maximum from i to j-1 as the difficulty of the current day.
- Recursively solve for jobs starting at j with d-1 days.
Return the minimum total difficulty found.

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = {}

        def dfs(i, d):
            if (i, d) in dp:
                return dp[(i, d)]

            maxi = jobDifficulty[i]
            if d == 1:
                idx = i
                while i < n:
                    maxi = max(maxi, jobDifficulty[i])
                    i += 1
                dp[(idx, d)] = maxi
                return maxi

            res = float("inf")
            for j in range(i + 1, n):
                res = min(res, maxi + dfs(j, d - 1))
                maxi = max(maxi, jobDifficulty[j])
            dp[(i, d)] = res
            return res

        return dfs(0, d)

Time & Space Complexity

Time complexity: $O(n ^ 2 * d)$
Space complexity: $O(n * d)$

Where $n$ is the number of jobs and $d$ is the number of days.

3. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down recursion into an iterative bottom-up approach. Define dp[i][day] as the minimum difficulty to schedule jobs from index i onward using exactly day days. We fill the table starting from the last day and work backward. For each state, we try all valid partitions of jobs for the current day and combine with the precomputed result for remaining days.

Algorithm

Create a 2D DP table where dp[i][day] represents the minimum difficulty starting from job i with day days remaining.
Initialize dp[n][0] = 0 (no jobs, no days needed).
Iterate day from 1 to d:
- For each starting position i from n-1 down to 0:
  - Try ending the current day at each position j from i to n-day.
  - Track the running maximum as the day's difficulty.
  - Update dp[i][day] with the minimum of max + dp[j+1][day-1].
Return dp[0][d].

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = [[float("inf")] * (d + 1) for _ in range(n + 1)]
        dp[n][0] = 0

        for day in range(1, d + 1):
            for i in range(n - 1, -1, -1):
                maxi = 0
                for j in range(i, n - day + 1):
                    maxi = max(maxi, jobDifficulty[j])
                    dp[i][day] = min(dp[i][day], maxi + dp[j + 1][day - 1])

        return dp[0][d]

Time & Space Complexity

Time complexity: $O(n ^ 2 * d)$
Space complexity: $O(n * d)$

Where $n$ is the number of jobs and $d$ is the number of days.

4. Dynamic Programming (Space Optimized)

Intuition

Notice that when computing dp[i][day], we only need values from dp[j][day-1] for j > i. This means we only need the previous day's row, not the entire 2D table. We can reduce space by using a single 1D array and updating it carefully. By processing positions from left to right within each day, we ensure that when we read dp[j+1], it still holds the value from the previous day.

Algorithm

Create a 1D DP array of size n+1, initialized to infinity except dp[n] = 0.
Iterate day from 1 to d:
- For each starting position i from 0 to n-day:
  - Reset dp[i] to infinity.
  - Track the running maximum while iterating j from i to n-day.
  - Update dp[i] with the minimum of max + dp[j+1].
Return dp[0].

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = [float("inf")] * (n + 1)
        dp[n] = 0

        for day in range(1, d + 1):
            for i in range(n - day + 1):
                maxi = 0
                dp[i] = float("inf")
                for j in range(i, n - day + 1):
                    maxi = max(maxi, jobDifficulty[j])
                    dp[i] = min(dp[i], maxi + dp[j + 1])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n ^ 2 * d)$
Space complexity: $O(n)$

Where $n$ is the number of jobs and $d$ is the number of days.

5. Monotonic Decreasing Stack

Intuition

The bottleneck in the previous approaches is finding the optimal partition for each day, which requires checking all possible ending positions. We can speed this up using a monotonic stack. The key insight is that when a new job has a higher difficulty than previous jobs in the current day, it becomes the new maximum and we can efficiently update our DP values. By maintaining a decreasing stack of job indices, we can quickly determine how previous partitions would change when extended to include the current job.

Algorithm

Create a DP array to store minimum difficulty ending at each position.
For each day from 1 to d:
- Create a new DP array for the current day.
- Use a monotonic decreasing stack to track job indices.
- For each job i:
  - Initialize: current job starts a new segment after the previous day's best ending.
  - While the stack is not empty and the top job has difficulty <= current job:
    - Pop the top and update the current DP by potentially replacing that job's max with the current job's difficulty.
  - If the stack is not empty, also consider inheriting the DP value from the stack top (the current job is dominated by a larger previous job).
  - Push the current index onto the stack.
Return the last element of the final DP array.

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1

        dp = [float("inf")] * n
        for day in range(1, d + 1):
            next_dp = [float("inf")] * n
            stack = []
            for i in range(day - 1, n):
                next_dp[i] = dp[i - 1] + jobDifficulty[i] if i > 0 else jobDifficulty[i]
                while stack and jobDifficulty[stack[-1]] <= jobDifficulty[i]:
                    j = stack.pop()
                    next_dp[i] = min(next_dp[i], next_dp[j] - jobDifficulty[j] + jobDifficulty[i])
                if stack:
                    next_dp[i] = min(next_dp[i], next_dp[stack[-1]])
                stack.append(i)
            dp = next_dp

        return dp[-1]

Time & Space Complexity

Time complexity: $O(n * d)$
Space complexity: $O(n)$

Where $n$ is the number of jobs and $d$ is the number of days.

Common Pitfalls

Forgetting the Impossible Case

A common mistake is not checking whether it is possible to schedule the jobs. If the number of jobs n is less than the number of days d, there is no valid schedule since each day must have at least one job. Failing to return -1 in this case leads to incorrect results or runtime errors.

Incorrect Day Difficulty Calculation

The difficulty of a day is the maximum job difficulty among all jobs scheduled that day, not the sum. Some implementations mistakenly accumulate job difficulties instead of tracking the running maximum, leading to inflated results.

Off-by-One Errors in Loop Bounds

When partitioning jobs across days, you must leave enough jobs for remaining days. For example, if you have d days left and are at position i, you can only extend the current day up to position n - d. Failing to enforce this constraint can result in invalid states where some days have no jobs.

Integer Overflow in DP Initialization

When initializing DP values to represent "infinity," using INT_MAX directly can cause overflow when adding to it. Use a safe large value like INT_MAX / 2 or check for overflow before arithmetic operations.

Misunderstanding the State Transitions

In the optimized approaches, confusing when to add the current day's difficulty versus when to continue accumulating jobs for the same day leads to incorrect answers. The key is recognizing that ending a day means adding cur_max to the result and resetting for the next day.