Minimum Difficulty Of A Job Schedule - Leetcode Solution

Problem statement:

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 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 in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of ith job is jobDifficulty[i].

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

Solution:

Approach:

This problem can be solved using dynamic programming.

Create a two-dimensional array dp where dp[i][j] represents the minimum possible difficulty to schedule first i jobs in j-1 days. The idea is to find all the valid k values, where k <= i and k >= j. Then, for every valid k, we can find the maximum value of jobDifficulty in the interval [k, i] and add it to the minimum difficulty of scheduling first k jobs in j-1 days.

dp[i][j] = min(dp[k][j-1] + max(jobDifficulty[k+1:i+1]))

Start with dp[0][0] = 0, dp[0][j] = infinity, for j > 0. We can set dp[k][j] = infinity for k > j, as we cannot schedule k jobs in j days.

To find the maximum value in an interval, we can use a segment tree.

The final answer will be dp[n][d], where n is the number of jobs.

Code:

The following is the implementation of the above approach.

1