Minimum Difficulty of a Job Schedule

Problem Description

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th 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 i-th job is jobDifficulty[i]. Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Key Insights

• The number of jobs must be at least equal to the number of days d. If not, return -1.
• The total difficulty can be minimized by carefully partitioning the jobs across the available days.
• Use dynamic programming to keep track of the minimum difficulty at each day and job index.

Space and Time Complexity

Time Complexity: O(n * d^2), where n is the number of jobs and d is the number of days.
Space Complexity: O(n * d), for the DP table.

Solution

We can solve this problem using dynamic programming. We'll create a DP table where dp[i][j] represents the minimum difficulty to schedule the first i jobs in j days. The main idea is to iterate through each job and each day, and for each combination, compute the maximum difficulty of jobs scheduled on that day while minimizing the overall difficulty.

1. Check if the number of jobs is less than d. If yes, return -1.
2. Initialize a DP array with size (n+1) x (d+1) where n is the length of jobDifficulty.
3. Iterate over the number of days, and for each day, iterate over the jobs, calculating the maximum job difficulty for the current partition.
4. Update the DP table by considering the minimum difficulty from previous partitions.

Code Solutions