# Minimum Difficulty of a Job Schedule
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule)
Canonical: https://scaleengineer.com/dsa/problems/minimum-difficulty-of-a-job-schedule
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Turvo](https://scaleengineer.com/companies/turvo)
---
## 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.

You are given an integer array `jobDifficulty` and an integer `d`. The difficulty of the `ith` job is `jobDifficulty[i]`.

Return _the minimum difficulty of a job schedule_. If you cannot find a schedule for the jobs return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-difficulty-of-a-job-schedule/image0.png) 

**Input:** jobDifficulty = [6,5,4,3,2,1], d = 2
**Output:** 7
**Explanation:** First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

**Example 2:**

**Input:** jobDifficulty = [9,9,9], d = 4
**Output:** -1
**Explanation:** If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

**Example 3:**

**Input:** jobDifficulty = [1,1,1], d = 3
**Output:** 3
**Explanation:** The schedule is one job per day. total difficulty will be 3.

**Constraints:**

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

# Approaches
## Recursion with Memoization (Top-Down DP)
This problem has optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. A straightforward way to approach DP is through top-down recursion with memoization.

We can define a recursive function `solve(i, d)` that calculates the minimum difficulty to schedule jobs from index `i` to the end of the array within `d` days. To find the solution for the original problem, we would call `solve(0, d)`.

In the function `solve(i, d)`, we try all possible ways to schedule the jobs for the current day. We can schedule jobs from `i` to `j`, where `j` is a valid split point. The difficulty for this day would be the maximum job difficulty in the range `[i, j]`. The remaining jobs from `j+1` to the end must then be scheduled in `d-1` days. We recursively call our function for this subproblem: `solve(j+1, d-1)`. We take the minimum over all possible split points `j`.

To avoid recomputing the same subproblem `(i, d)` multiple times, we use a 2D array `memo` to store the results. Before computing `solve(i, d)`, we check if the result is already in our memoization table.
**Time:** O(n^2 * d). There are `n * d` states for our `solve(i, daysLeft)` function. For each state, we iterate from `i` to `n - daysLeft`, which can be up to `O(n)` iterations. Inside the loop, we do constant time work (as the recursive call's result will be memoized). Thus, the total time complexity is `O(n * d * n) = O(n^2 * d)`. · **Space:** O(n * d), where `n` is the number of jobs and `d` is the number of days. This is for the memoization table `memo`. The recursion stack depth is at most `d`.
**Pros:** Relatively intuitive to formulate from the problem's recursive nature.; Correctly solves the problem within the given constraints.
**Cons:** The time and space complexity are not optimal.; Can lead to a `StackOverflowError` for very deep recursion, although `d` is small here, so it's not a major concern.
### Explanation
```java
class Solution {
    private int n;
    private int[] jobDifficulty;
    private int d;
    private int[][] memo;

    public int minDifficulty(int[] jobDifficulty, int d) {
        this.n = jobDifficulty.length;
        if (n < d) {
            return -1;
        }
        this.jobDifficulty = jobDifficulty;
        this.d = d;
        this.memo = new int[n][d + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        return solve(0, d);
    }

    private int solve(int i, int daysLeft) {
        // If we have already computed this subproblem, return the stored result.
        if (memo[i][daysLeft] != -1) {
            return memo[i][daysLeft];
        }

        // Base case: If only one day is left, we must do all remaining jobs.
        // The difficulty for this day is the max difficulty among the remaining jobs.
        if (daysLeft == 1) {
            int maxDifficulty = 0;
            for (int k = i; k < n; k++) {
                maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k]);
            }
            return memo[i][daysLeft] = maxDifficulty;
        }

        int minTotalDifficulty = Integer.MAX_VALUE;
        int maxDifficultyCurrentDay = 0;

        // Iterate through all possible split points 'j'.
        // We must leave at least 'daysLeft - 1' jobs for the remaining days.
        for (int j = i; j <= n - daysLeft; j++) {
            maxDifficultyCurrentDay = Math.max(maxDifficultyCurrentDay, jobDifficulty[j]);
            int remainingDifficulty = solve(j + 1, daysLeft - 1);
            
            // If the subproblem is solvable
            if (remainingDifficulty != Integer.MAX_VALUE) {
                minTotalDifficulty = Math.min(minTotalDifficulty, maxDifficultyCurrentDay + remainingDifficulty);
            }
        }

        return memo[i][daysLeft] = minTotalDifficulty;
    }
}
```
### Algorithm
1. **Base Case:** If the number of jobs `n` is less than the number of days `d`, it's impossible to schedule. Return -1.
2. **Recursive Function:** Define a function, say `solve(i, daysLeft)`, which computes the minimum difficulty to schedule jobs from index `i` to `n-1` in `daysLeft` days.
3. **Memoization:** Use a 2D array, `memo[i][daysLeft]`, to store the results of subproblems to avoid re-computation. Initialize it with a value like -1.
4. **Recursive Step:**
   - For the current day, we can take jobs from `i` to `j`. The number of remaining jobs `n - (j+1)` must be at least `daysLeft - 1`.
   - The difficulty for the current day is `max(jobDifficulty[i...j])`.
   - The difficulty for the remaining days is `solve(j+1, daysLeft - 1)`.
   - We iterate through all valid split points `j` (from `i` to `n - daysLeft`) and find the minimum total difficulty: `min(max(jobDifficulty[i...j]) + solve(j+1, daysLeft - 1))`. 
5. **Base Case for Recursion:** If `daysLeft` is 1, we must schedule all remaining jobs (`i` to `n-1`) on this day. The difficulty is `max(jobDifficulty[i...n-1])`.
6. **Return Value:** The final answer is the result of `solve(0, d)`. If the result is infinity (or a very large number used for initialization), it means no valid schedule was found, but our initial check `n < d` should handle this.

## Tabulation (Bottom-Up DP)
The top-down recursive solution can be converted into a bottom-up iterative solution, also known as tabulation. This approach builds the solution from the smallest subproblems up to the final problem. It avoids recursion overhead and can sometimes make space optimizations more apparent.

We define a 2D DP table, `dp[k][i]`, to store the minimum difficulty of scheduling the first `i` jobs in `k` days. We iterate through the days `k` from 1 to `d`, and for each day, we iterate through the jobs `i` from `k` to `n`. The value of `dp[k][i]` is determined by finding the best way to form the `k`-th day. If the `k`-th day includes jobs from `j` to `i-1`, the total difficulty would be the cost of scheduling the first `j` jobs in `k-1` days (`dp[k-1][j]`) plus the difficulty of the `k`-th day (`max(jobDifficulty[j...i-1])`). We minimize this over all possible `j`.
**Time:** O(n^2 * d). We have three nested loops: `k` from 1 to `d`, `i` from `k` to `n`, and `j` from `i-1` to `k-1`. This results in a cubic complexity relative to `n` if `d` is proportional to `n`, but since `d` is small, we state it as `O(n^2 * d)`. · **Space:** O(n * d). The standard tabulation uses a `(d+1) x (n+1)` table. This can be optimized to O(n) because computing the values for day `k` only requires the values from day `k-1`.
**Pros:** Eliminates recursion overhead, which can be slightly faster in practice.; The iterative structure makes space optimization more straightforward.
**Cons:** The time complexity is the same as the memoized recursion, `O(n^2 * d)`, which is not optimal.; Requires careful handling of loop bounds and indices.
### Explanation
```java
class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) {
            return -1;
        }

        // dp[k][i]: min difficulty for first i jobs in k days
        int[][] dp = new int[d + 1][n + 1];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE / 2); // Use a large value to prevent overflow
        }
        dp[0][0] = 0;

        for (int k = 1; k <= d; k++) {
            for (int i = k; i <= n; i++) {
                int maxDifficultyLastDay = 0;
                // j is the start index of the last day's jobs
                for (int j = i - 1; j >= k - 1; j--) {
                    maxDifficultyLastDay = Math.max(maxDifficultyLastDay, jobDifficulty[j]);
                    dp[k][i] = Math.min(dp[k][i], dp[k-1][j] + maxDifficultyLastDay);
                }
            }
        }

        return dp[d][n] == Integer.MAX_VALUE / 2 ? -1 : dp[d][n];
    }
}
```
**Space-Optimized Version:**
```java
class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) return -1;

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        for (int k = 1; k <= d; k++) {
            int[] next_dp = new int[n + 1];
            Arrays.fill(next_dp, Integer.MAX_VALUE / 2);
            for (int i = k; i <= n; i++) {
                int maxDifficultyLastDay = 0;
                for (int j = i - 1; j >= k - 1; j--) {
                    maxDifficultyLastDay = Math.max(maxDifficultyLastDay, jobDifficulty[j]);
                    next_dp[i] = Math.min(next_dp[i], dp[j] + maxDifficultyLastDay);
                }
            }
            dp = next_dp;
        }

        return dp[n] == Integer.MAX_VALUE / 2 ? -1 : dp[n];
    }
}
```
### Algorithm
1. **State Definition:** Let `dp[k][i]` be the minimum difficulty to schedule the first `i` jobs (from index 0 to `i-1`) in `k` days.
2. **Initialization:** Create a `dp` table of size `(d+1) x (n+1)` and initialize all values to infinity, except `dp[0][0] = 0`.
3. **Base Case (k=1):** For one day, `dp[1][i]` is the maximum difficulty of the first `i` jobs. This can be computed iteratively: `dp[1][i] = max(dp[1][i-1], jobDifficulty[i-1])`.
4. **Transitions:** Iterate through the number of days `k` from 2 to `d`. For each `k`, iterate through the number of jobs `i` from `k` to `n`. To compute `dp[k][i]`, we try all possible split points for the `k`-th day. Let the `k`-th day consist of jobs from index `j` to `i-1`. The previous `k-1` days must have scheduled jobs from 0 to `j-1`. The recurrence relation is:
   `dp[k][i] = min(dp[k][i], dp[k-1][j] + max(jobDifficulty[j...i-1]))` for `j` from `k-1` to `i-1`.
5. **Result:** The final answer is `dp[d][n]`.
6. **Space Optimization:** Notice that `dp[k]` only depends on `dp[k-1]`. We can optimize the space to `O(n)` by using only two rows (or one, with careful updates) of the DP table.

## Optimized Bottom-Up DP with Monotonic Stack
The `O(n^2 * d)` complexity of the previous approaches comes from the innermost loop that recalculates the minimum over all possible split points. This calculation can be optimized. For a fixed day `k`, when computing `dp_curr[i]`, we are essentially solving `min_{j<i} (dp_prev[j] + max(jobDifficulty[j...i-1]))`.

This structure can be optimized using a monotonic stack. The stack helps us maintain candidates for the split point `j` in a way that lets us compute the minimum in amortized `O(1)` time instead of `O(n)`.

We process jobs one by one. The stack stores indices of jobs in decreasing order of their difficulty. When a new job `i` arrives with a higher difficulty than the job at the top of the stack, it means job `i` will be the maximum for a certain range. The stack helps us efficiently calculate the cost contribution of these ranges. By cleverly updating the minimum cost associated with stack segments, we can find the optimal `dp_curr[i]` quickly.
**Time:** O(n * d). The outer loop runs `d` times. The inner loop runs `n` times. Inside the inner loop, each element is pushed onto and popped from the stack at most once over the course of the loop. Therefore, the stack operations take amortized O(1) time, leading to a total time complexity of O(n * d). · **Space:** O(n). We only need to store the DP results for the previous day to compute the current day. The stack also takes at most O(n) space.
**Pros:** Optimal time complexity, making it very fast.; Optimal space complexity.
**Cons:** The logic is significantly more complex and less intuitive than the standard DP approaches.; Implementation can be tricky and error-prone.
### Explanation
```java
class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) {
            return -1;
        }

        int[] dp = new int[n];
        int maxDifficulty = 0;
        for (int i = 0; i < n; i++) {
            maxDifficulty = Math.max(maxDifficulty, jobDifficulty[i]);
            dp[i] = maxDifficulty;
        }

        for (int k = 2; k <= d; k++) {
            int[] dpNext = new int[n];
            Arrays.fill(dpNext, Integer.MAX_VALUE);
            // Stack stores indices
            Deque<Integer> stack = new ArrayDeque<>();
            
            for (int i = k - 1; i < n; i++) {
                // The cost to schedule the first i jobs (0..i-1) in k-1 days.
                // This is the value we'd use if the k-th day starts at job i.
                int minPrevCost = dp[i - 1];
                
                while (!stack.isEmpty() && jobDifficulty[stack.peek()] <= jobDifficulty[i]) {
                    // jobDifficulty[i] is greater, so it becomes the max for the segment
                    // previously covered by stack.peek(). We merge the segments.
                    minPrevCost = Math.min(minPrevCost, dp[stack.pop()]);
                }

                if (!stack.isEmpty()) {
                    // The last day starts after stack.peek(). The max difficulty for this
                    // part of the last day is jobDifficulty[i].
                    // The cost is the min cost of the previous day's schedule ending at stack.peek(),
                    // plus the max difficulty of the segment from stack.peek() to i.
                    // dp[stack.peek()] already contains this min cost.
                    dpNext[i] = Math.min(dpNext[i], dp[stack.peek()] + jobDifficulty[i]);
                }
                
                // The last day starts at the beginning of the merged segment.
                // The cost is minPrevCost + jobDifficulty[i].
                dpNext[i] = Math.min(dpNext[i], minPrevCost + jobDifficulty[i]);
                
                // We store the min cost for schedules ending at `i` for day `k`
                // This is a bit tricky. The value we need for future calculations is the minimum
                // cost for day k-1 ending at various points. The logic above handles this by
                // passing `minPrevCost` forward.
                // For the stack, we need to associate the min cost of day k-1 ending at that index.
                // A simpler way is to just use the dp array directly.
                dp[i] = minPrevCost; // Store the min cost for the segment starting after this index.
                stack.push(i);
            }
            // This is a slightly different but working formulation of the stack logic.
            // Let's use a more standard one for clarity.
            
            // Standard O(nd) implementation:
            stack.clear();
            for (int i = k - 1; i < n; i++) {
                int prevDayCost = dp[i - 1];
                while (!stack.isEmpty() && jobDifficulty[stack.peek()] <= jobDifficulty[i]) {
                    int j = stack.pop();
                    prevDayCost = Math.min(prevDayCost, dp[j]);
                }
                if (!stack.isEmpty()) {
                    dpNext[i] = dp[stack.peek()] + jobDifficulty[i];
                }
                dpNext[i] = Math.min(dpNext[i], prevDayCost + jobDifficulty[i]);
                dp[i] = prevDayCost;
                stack.push(i);
            }
            dp = dpNext;
        }

        return dp[n - 1];
    }
}
```
*Note: The provided code shows one way to implement the O(n*d) logic. The core idea is that for each day `k`, a new `dp` array is computed in `O(n)` time using the `dp` array from day `k-1` and a monotonic stack.*
### Algorithm
1. **DP State and Recurrence:** Use the same space-optimized DP setup as the previous approach. Let `dp[i]` be the min difficulty for the first `i` jobs in `k-1` days. We want to compute `dp_next[i]` for day `k`.
   `dp_next[i] = min_{j=k-1 to i-1} (dp[j] + max(jobDifficulty[j...i-1]))`.
2. **Monotonic Stack:** For each day `k`, we use a monotonic stack to optimize the calculation of `dp_next`. The stack will store indices `p` such that `jobDifficulty[p]` is strictly decreasing.
3. **Iteration:** We iterate `i` from `k` to `n` to compute `dp_next[i]`.
4. **Stack Maintenance:** When considering job `i-1`, we maintain the stack's property. We pop indices `p` from the stack if `jobDifficulty[p] <= jobDifficulty[i-1]`. This is because `jobDifficulty[i-1]` will 'shadow' these smaller or equal difficulties for all future calculations.
5. **Cost Calculation:** As we pop from the stack, we track the minimum `dp[p]` value of the jobs being merged into the new segment dominated by `jobDifficulty[i-1]`. Let's call this `min_prev_cost`.
6. **DP Update:** After updating the stack, `dp_next[i]` can be calculated efficiently. The stack partitions the jobs `0...i-1` into segments, each with a specific maximum difficulty (defined by the stack elements). The cost for a segment starting at index `p` is `min_prev_cost_for_p + jobDifficulty[p]`. We can find the minimum of these costs in `O(1)` by carrying over the minimum from the previous step.
7. **Final Result:** After `d` iterations, `dp[n]` will hold the answer.

# Solutions
### Java

```java
class Solution {
public
  int minDifficulty(int[] jobDifficulty, int d) {
    final int inf = 1 << 30;
    int n = jobDifficulty.length;
    int[][] f = new int[n + 1][d + 1];
    for (var g : f) {
      Arrays.fill(g, inf);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= Math.min(d, i); ++j) {
        int mx = 0;
        for (int k = i; k > 0; --k) {
          mx = Math.max(mx, jobDifficulty[k - 1]);
          f[i][j] = Math.min(f[i][j], f[k - 1][j - 1] + mx);
        }
      }
    }
    return f[n][d] >= inf ? -1 : f[n][d];
  }
}

```

### Python

```python
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]

```

### CPP

```cpp
class Solution {
public:
  int minDifficulty(vector<int> &jobDifficulty, int d) {
    int n = jobDifficulty.size();
    int f[n + 1][d + 1];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= min(d, i); ++j) {
        int mx = 0;
        for (int k = i; k; --k) {
          mx = max(mx, jobDifficulty[k - 1]);
          f[i][j] = min(f[i][j], f[k - 1][j - 1] + mx);
        }
      }
    }
    return f[n][d] == 0x3f3f3f3f ? -1 : f[n][d];
  }
};

```