0 like 0 dislike
2,620 views

All past online assesments of Amazon can be found using the tag "amazon_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/amazon_oa

edited | 2,620 views

0 like 0 dislike

You want to schedule a list of jobs in `d` days. Jobs are dependent (i.e To work on the `ith` 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 `ith` 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.
```

Constraints:

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

`Code : `

``````const minDifficulty = (A, D) => {
let n = A.length, inf = Infinity, maxd;

if (n < D) return -1;

let dp = new Array(n + 1).fill(Infinity);
dp[n] = 0;

for (let d = 1; d <= D; d++) {
for (let i = 0; i <= n - d; i++) {
maxd = 0, dp[i] = inf;

for (let j = i; j <= n - d; j++) {
maxd =  Math.max(maxd, A[j]);
dp[i] = Math.min(dp[i], maxd + dp[j + 1]);
}
}
}

return dp[0];
}``````
by Expert (111,330 points)