Problem 1335

(Last updated: )

Question

You want to schedule a list of jobs in $\texttt{d}$ days. Jobs are dependent (i.e To work on the $\texttt{i}$-th job, you have to finish all the jobs $\texttt{j}$ where $\texttt{0} \leq \texttt{j} < \texttt{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 $\texttt{d}$ days. The difficulty of a day is the maximum difficulty of a job done on that day. You are given an integer array $\texttt{jobDifficulty}$ and an integer $\texttt{d}$. The difficulty of the $\texttt{i}$-th job is $\texttt{jobDifficulty[i]}$. Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Solution

We will approach this problem as a two dimensional dynamic programming problem

Observation and reformulation

One natural way to think about this problem is as a sticks and stones (type) counting problem. We have $\texttt{n= len(jobDifficulty)}$ stones weighted by difficulty and $\texttt{d-1}$ sticks, that we need to place between the stones so that they form $\texttt{d}$ groups. Say we have groups $G_{i_1},\dots, G_{i_d}$, where $i_j$ is the index at which group $G_{i_j}$ starts. We need to find positions $i_j$ such that

$$\sum_{j=1}^d \max_k \{g_k | g_k \in G_{i_j}\}$$

is minimized.

Observation: Instead of solving this problem all in one go, we can solve the problems for progressively longer slices of the given $\texttt{jobDifficulty}$ string, with progressively larger number of cuts $\leq d-1$. This is best illustrated with an example:

Suppose $\texttt{jobDifficulty} = [3,4,1,6,15,2,4,6]$ (with indices going from $0$ to $7$) and $d= 4$. In this case, we are allowed to put $3$ cuts in the array. To do this, lets iterate over the possible places the last cut can go. The last cut can go after indices $k=2,3,4,5,6$. This is because, if the last cut happened before index $2$, we will not have enough space to put the other two cuts. For each of these options, we can recursively calculate the weekly schedule difficulty by calculating
$$\texttt{max(jobDifficulty[k+1:]) + minDifficulty(jobDifficulty[:k+1], d-1)} \qquad (\star)$$
The minimum of these is our answer. But this would involve recursing over smaller and smaller slices of the given array, and hence a lot of duplicate computations.

Main idea:

  • To help with memory management and speed, we can memoize a lot of repeated calculations.
  • Construct a $\texttt{d} \times \texttt{n}$ array $\texttt{dp}$ with every entry initialized to $-1$.
  • $\texttt{dp[i][j]}$ stores the optimal difficulty for the first $\texttt{i}$ entries of the array, with a maximum of $\texttt{j}$ cuts allowed.
  • The base cases are when $j=0$, in which case, we simply return $\texttt{max(s)}$ where $\texttt{s=jobDifficulty[:i+1]}$.
  • When $\texttt{j}\neq \texttt{0}$, then given $\texttt{s}$, we can place our last cut at indices $\texttt{k= i-1,} \dots, \texttt{j+1}$. For each $\texttt{k}$, we compute $(\star)$
    • Note: $\texttt{minDifficulty(s[:k+1], j-1)}$ (if it is valid) is stored as a non $-1$ entry in $\texttt{dp[k][j-1]}$
  • Return $\texttt{dp[n-1][d-1]}$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
    def helper(self, dp, s, i, j):
        if(j==0):
            return(max(s))
        if(dp[i][j] != -1):
            return dp[i][j]
        min_schedule = float('inf')
        for k in range(len(s), j, -1):
            work_today = max(s[k-1: len(s)])
            schedule = work_today + helper(self, dp, s[:k-1], len(s[:k-1])-1, j-1)
            if(schedule <= min_schedule):
                min_schedule = schedule
        return min_schedule

    
    
    n = len(jobDifficulty)
    dp = [[-1]*d for j in range(n)]
    for i in range(n):
        max_cuts = min(i,d-1)
        for j in range(max_cuts+1):
            dp[i][j] = helper(self, dp, jobDifficulty[:i+1], i, j)
    return dp[n-1][d-1]

Comments:

Time complexity: O($\texttt{n}^2\texttt{d}$).

At the time of submission, the above solution passes leetcode submission cases in 6000ms, beating 5.25% of users. It uses 17.58MB of memory, beating 55.46% of users.