Minimum Difficulty of a Job Schedule

How it works

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.

Steps

1. Create a DP array to store minimum difficulty ending at each position.
2. 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.
3. Return the last element of the final DP array.

Complexity

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

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

Things to watch for

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.

from typing import List

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]

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        if (n < d) return -1;

        vector<int> dp(n, INT_MAX / 2);

        for (int day = 1; day <= d; day++) {
            vector<int> nextDp(n, INT_MAX / 2);
            stack<int> st;
            for (int i = day - 1; i < n; i++) {
                nextDp[i] = (i > 0 ? dp[i - 1] : 0) + jobDifficulty[i];
                while (!st.empty() && jobDifficulty[st.top()] <= jobDifficulty[i]) {
                    int j = st.top(); st.pop();
                    nextDp[i] = min(nextDp[i], nextDp[j] - jobDifficulty[j] + jobDifficulty[i]);
                }
                if (!st.empty()) {
                    nextDp[i] = min(nextDp[i], nextDp[st.top()]);
                }
                st.push(i);
            }
            dp = nextDp;
        }

        return dp[n - 1];
    }
};