Page Contents

*Minimum Difficulty of a Job Schedule Solution*

*Minimum Difficulty of a Job Schedule Solution*

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]`

.

Also See: Amazon OA Online Assessment 2021 Questions and Answers

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 = 2Output:7Explanation: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 = 4Output:-1Explanation: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 = 3Output:3Explanation:The schedule is one job per day. total difficulty will be 3.

**Example 4:**

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

**Example 5:**

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

**Constraints:**

`1 <= jobDifficulty.length <= 300`

`0 <= jobDifficulty[i] <= 1000`

`1 <= d <= 10`

*Solution*

*Solution*

*Program C++*

Consider dp[i][j] as the min difficulty for first i jobs in first j days. Since every day should be assinged atleast one job, ith job is done on jth day. By the same logic atleast first (j-1) jobs should be left for first (j-1) days. Now let us schedule jobs from k to i on the jth day, k varies from j to i.

class Solution { public: int minDifficulty(vector<int>& a, int d) { int n=a.size(); if(n<d) return -1; int dp[n+1][d+1]; fill_n(&dp[0][0],(n+1)*(d+1),1e9); dp[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>=j;k--){ mx=max(mx,a[k-1]); if(dp[k-1][j-1]<1e9) dp[i][j]=min(dp[i][j],mx+dp[k-1][j-1]); } } } return dp[n][d]; } };

*Program Java*

class Solution { public int minDiff(int[] jobs, int start, int n, int d, int[][] dp){ if (n > d) return 0; //if calculated before if (dp[start][n] != -1) return dp[start][n]; //int the last step, we need to take the maximum of the rest of elements if (n == d){ int currentMax = Integer.MIN_VALUE; for (int i=start;i<jobs.length;i++){ currentMax = Math.max(currentMax, jobs[i]); } dp[start][n] = currentMax; return currentMax; } int min = Integer.MAX_VALUE; int currentMax = Integer.MIN_VALUE; //loop until before jobs.length-(d-n) to make sure we have enough jobs for the rest of the days for (int i=start;i<jobs.length-(d-n);i++){ currentMax = Math.max(currentMax, jobs[i]); min = Math.min(min, minDiff(jobs, i+1, n+1, d, dp)+currentMax); } dp[start][n] = min; return min; } public int minDifficulty(int[] jobDifficulty, int d) { //if days is more than the jobs, then we can't proceed if (d > jobDifficulty.length) return -1; //init our dynamic programming array int[][] dp = new int[jobDifficulty.length][d+1]; for (int i=0;i<dp.length;i++){ for (int j=0;j<dp[0].length;j++) dp[i][j] = -1; } return minDiff(jobDifficulty,0, 1, d, dp); } }

*Program Python*

""" dp[i][k] := minimum difficulty of a k days job schedule, D[:i]. maxInRange[i][j] := max(D[i:j+1]) """ class Solution(object): def minDifficulty(self, D, K): if not D or not K or K>len(D): return -1 N = len(D) maxInRange = [[0 for _ in xrange(N)] for _ in xrange(N)] for i in xrange(N): maxInRange[i][i] = D[i] for l in xrange(2, N+1): for i in xrange(N): j = i+l-1 if j>=N: continue maxInRange[i][j] = max(maxInRange[i+1][j-1], D[i], D[j]) dp = [[float('inf') for _ in xrange(K+1)] for _ in xrange(N+1)] dp[0][0] = 0 for i in xrange(1, N+1): for k in xrange(1, min(i, K)+1): for j in xrange(k, i+1): dp[i][k] = min(dp[i][k], dp[j-1][k-1]+maxInRange[j-1][i-1]) #if you don't pre-calculate maxInRange #dp[i][k] = min(dp[i][k], dp[j-1][k-1]+max(D[j-1:i])) return dp[N][K]

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution

**Amazon Online Assessment Questions:**

*Robot Bounded in Box**Number Game**Find All Combination of Numbers Sum to Target / Shopping Options**Fill the Truck**Music Pairs**Slowest key**Five Star Seller**Split String Into Unique Primes**Storage Optimization**Minimum Difficulty of a Job Schedule**Autoscale Policy, Utilization Check**Optimal Utilization**Merge Two Sorted Lists**Two Sum Unique Pairs**Shopping Patterns**Reorder Data in Log Files**Top K Frequent Words**Trees Height**Counting Binary Substrings Amazon OA Solution**Grid Connections Amazon OA Solution**Shipment Imbalance Amazon OA Solution**Max Profit Amazon OA Solution**Find Lowest Price Amazon OA Solution**Simple Cipher Amazon OA Solution**Decode String Frequency Amazon OA Solution**Valid Discount Coupons Amazon OA Solution**Count Maximum Teams Amazon OA Solution**Minimum Coin Flips Amazon OA Solution*