Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1335.html

1335. Minimum Difficulty of a Job Schedule (Hard)

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

Given an array of integers 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.

 

Example 1:

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.

Example 4:

Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:

Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

 

Constraints:

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

Related Topics:
Dynamic Programming

Solution 1. DP

Let dp[d][i] be the answer for the subproblem with d days at ith job.

Let mx[i][j] be the maximum value in A[i..j].

dp[d][i] = min( dp[d-1][j-1] + mx[j][i] | d-1 <= j <= i )
// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(N^2 * D)
// Space: O(N^2 + ND)
class Solution {
    typedef long long LL;
    inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
    int minDifficulty(vector<int>& A, int D) {
        int N = A.size();
        if (D > N) return -1;
        vector<vector<LL>> mx(N, vector<LL>(N)), dp(D + 1, vector<LL>(N, 1e9));
        for (int i = 0; i < N; ++i) {
            for (int j = i; j < N; ++j) mx[i][j] = *max_element(A.begin() + i, A.begin() + j + 1);
        }
        for (int i = 0; i < N; ++i) dp[1][i] = mx[0][i];
        for (int d = 2; d <= D; ++d) {
            for (int i = d - 1; i < N; ++i) {
                for (int j = d - 1; j <= i; ++j) {
                    setMin(dp[d][i], dp[d - 1][j - 1] + mx[j][i]);
                }
            }
        }
        return dp[D][N - 1];
    }
};

Solution 2. DP

We can compute the mx while computing dp instead of computing mx array beforehand.

// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(N^2 * D)
// Space: O(ND) 
class Solution {
    typedef long long LL;
    inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
    int minDifficulty(vector<int>& A, int D) {
        int N = A.size(), inf = 1e9;
        if (D > N) return -1;
        vector<vector<LL>> dp(D + 1, vector<LL>(N, inf));
        for (int i = 0; i < N; ++i) dp[1][i] = i == 0 ? A[0] : max(dp[1][i - 1], (LL)A[i]);
        for (int d = 2; d <= D; ++d) {
            for (int i = d - 1; i < N; ++i) {
                int mx = 0;
                for (int j = i; j >= d - 1; --j) {
                    mx = max(mx, A[j]);
                    setMin(dp[d][i], dp[d - 1][j - 1] + mx);
                }
            }
        }
        return dp[D][N - 1];
    }
};

Solution 3. DP

Since dp[d][i] is dependent on dp[d-1][j-1] and j <= i, we can flip the loop direction and just need 1D dp array.

// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(NND)
// Space: O(N)
class Solution {
    typedef long long LL;
    inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
    int minDifficulty(vector<int>& A, int D) {
        int N = A.size(), inf = 1e9;
        if (D > N) return -1;
        vector<LL> dp(N);
        for (int i = 0; i < N; ++i) dp[i] = i == 0 ? A[0] : max(dp[i - 1], (LL)A[i]);
        for (int d = 2; d <= D; ++d) {
            for (int i = N - 1; i >= d - 1; --i) {
                int mx = 0;
                dp[i] = inf;
                for (int j = i; j >= d - 1; --j) {
                    mx = max(mx, A[j]);
                    setMin(dp[i], dp[j - 1] + mx);
                }
            }
        }
        return dp[N - 1];
    }
};

Solution 4. DP + Monotonic Min Stack

TODO https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/discuss/490316/JavaC%2B%2BPython3-DP-O(nd)-Solution

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/discuss/495000/C%2B%2B-0ms!-O(d*n)-time-O(n)-space.-DP-%2B-MonotonicMinimum-Stack

  • class Solution {
        public int minDifficulty(int[] jobDifficulty, int d) {
            if (jobDifficulty == null)
                return -1;
            int length = jobDifficulty.length;
            if (length < d)
                return -1;
            if (length == d) {
                int sum = 0;
                for (int difficulty : jobDifficulty)
                    sum += difficulty;
                return sum;
            }
            int[] maxDifficultyRight = new int[length];
            maxDifficultyRight[length - 1] = jobDifficulty[length - 1];
            for (int i = length - 2; i >= 0; i--)
                maxDifficultyRight[i] = Math.max(maxDifficultyRight[i + 1], jobDifficulty[i]);
            int[][] dp = new int[d][length];
            dp[0][0] = jobDifficulty[0];
            for (int i = 1; i <= length - d; i++)
                dp[0][i] = Math.max(dp[0][i - 1], jobDifficulty[i]);
            for (int i = 1; i < d; i++) {
                int start = i, end = length - d + i;
                int prevEnd = start - 1;
                for (int j = start; j <= end; j++) {
                    dp[i][j] = dp[i - 1][j - 1] + jobDifficulty[j];
                    int max = jobDifficulty[j];
                    for (int k = j - 2; k >= prevEnd; k--) {
                        max = Math.max(max, jobDifficulty[k + 1]);
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + max);
                    }
                }
            }
            return dp[d - 1][length - 1];
        }
    }
    
    ############
    
    class Solution {
        public int minDifficulty(int[] jobDifficulty, int d) {
            int n = jobDifficulty.length;
            final int inf = 1 << 30;
            int[][] f = new int[n + 1][d + 1];
            for (int[] g : f) {
                Arrays.fill(g, inf);
            }
            f[0][0] = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= d; ++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 ? f[n][d] : -1;
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
    // Time: O(N^2 * D)
    // Space: O(N^2 + ND)
    class Solution {
        typedef long long LL;
        inline void setMin(LL &a, LL b) { a = min(a, b); }
    public:
        int minDifficulty(vector<int>& A, int D) {
            int N = A.size();
            if (D > N) return -1;
            vector<vector<LL>> mx(N, vector<LL>(N)), dp(D + 1, vector<LL>(N, 1e9));
            for (int i = 0; i < N; ++i) {
                for (int j = i; j < N; ++j) mx[i][j] = *max_element(A.begin() + i, A.begin() + j + 1);
            }
            for (int i = 0; i < N; ++i) dp[1][i] = mx[0][i];
            for (int d = 2; d <= D; ++d) {
                for (int i = d - 1; i < N; ++i) {
                    for (int j = d - 1; j <= i; ++j) {
                        setMin(dp[d][i], dp[d - 1][j - 1] + mx[j][i]);
                    }
                }
            }
            return dp[D][N - 1];
        }
    };
    
  • 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, x in enumerate(jobDifficulty, 1):
                for j in range(1, d + 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 f[n][d] if f[n][d] != inf else -1
    
    
  • func minDifficulty(jobDifficulty []int, d int) int {
    	n := len(jobDifficulty)
    	f := make([][]int, n+1)
    	const inf = 1 << 30
    	for i := range f {
    		f[i] = make([]int, d+1)
    		for j := range f[i] {
    			f[i][j] = inf
    		}
    	}
    	f[0][0] = 0
    	for i := 1; i <= n; i++ {
    		for j := 1; j <= d; j++ {
    			mx := 0
    			for k := i; k > 0; k-- {
    				mx = max(mx, jobDifficulty[k-1])
    				f[i][j] = min(f[i][j], f[k-1][j-1]+mx)
    			}
    		}
    	}
    	if f[n][d] == inf {
    		return -1
    	}
    	return f[n][d]
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    
  • function minDifficulty(jobDifficulty: number[], d: number): number {
        const n = jobDifficulty.length;
        const inf = 1 << 30;
        const f: number[][] = new Array(n + 1)
            .fill(0)
            .map(() => new Array(d + 1).fill(inf));
        f[0][0] = 0;
        for (let i = 1; i <= n; ++i) {
            for (let j = 1; j <= Math.min(d, i); ++j) {
                let mx = 0;
                for (let 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 ? f[n][d] : -1;
    }
    
    

All Problems

All Solutions