# Job Scheduling to Minimize Difficulty - Amazon Top Interview Questions

### Problem Statement :

```You are given a list of integers jobs and an integer k. You want to finish all jobs in k days. The jobs must be done in order and a job must be done each day.

The difficulty of job i is jobs[i] and the difficulty of doing a list of jobs on a day is defined to be the maximum difficulty job performed on that day.

Return the minimum sum of the difficulties to perform the jobs over k days.

Constraints

n ≤ 500 where n is the length of jobs

k ≤ 10

Example 1

Input

jobs = [1, 2, 3, 5, 2]

k = 2

Output

6

Explanation

We do [1] the first day and then do [2, 3, 5, 2]. The total difficulty is 1 + max(2, 3, 5, 2) = 6.```

### Solution :

```                        ```Solution in C++ :

int solve(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n + 1);
fill(dp.begin() + 1, dp.end(), INT_MAX);
dp[0] = 0;
while (k--) {
vector<int> ndp(n + 1, INT_MAX);
for (int i = 0; i < nums.size(); i++) {
if (dp[i] == INT_MAX) continue;
int maxd = 0;
for (int j = i; j < nums.size(); j++) {
maxd = max(maxd, nums[j]);
ndp[j + 1] = min(ndp[j + 1], dp[i] + maxd);
}
}
dp.swap(ndp);
}
return dp[n];
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
/**
public int solve(int[] jobs, int k) {
if (jobs.length < k) {
return -1;
}

return helper(jobs, k, 0);
}
private int helper(int[] jobs, int k, int start) {

int max = -1;
int ans = Integer.MAX_VALUE;
int end = jobs.length - k;

if (k == 1) {
for (int i = start; i <= end; i++) {
max = Math.max(max, jobs[i]);
}

return max;
} else {
for (int i = start; i <= end; i++) {
max = Math.max(max, jobs[i]);
ans = Math.min(ans, max + helper(jobs, k - 1, i + 1));
}

return ans;
}
}
*/
int[][] m;
public int solve(int[] jobs, int k) {
if (jobs.length < k) {
return -1;
}
m = new int[k + 1][jobs.length];
return helper(jobs, k, 0);
}
private int helper(int[] jobs, int k, int start) {
if (m[k][start] > 0) {
return m[k][start];
}
int max = -1;
int ans = Integer.MAX_VALUE;
int end = jobs.length - k;

if (k == 1) {
for (int i = start; i <= end; i++) {
max = Math.max(max, jobs[i]);
}
m[k][start] = max;
return max;
} else {
for (int i = start; i <= end; i++) {
max = Math.max(max, jobs[i]);
ans = Math.min(ans, max + helper(jobs, k - 1, i + 1));
}
m[k][start] = ans;
return ans;
}
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, jobs, k):
N = len(jobs)

@lru_cache(None)
def traverse(idx, day, current_max):

if day > k:
return math.inf

if idx == N:
if k == day:
return current_max if current_max != -math.inf else 0
return math.inf

# choice-01 -> Stop the day with the current task and chill. (Lazy :D)
# choice-02: do the next task the same day so that you can chill later. (Eager :|)

val = jobs[idx]
choice_01 = max(current_max, val) + traverse(idx + 1, day + 1, -math.inf)
choice_02 = traverse(idx + 1, day, max(current_max, val))

return min(choice_01, choice_02)

return traverse(0, 0, -math.inf)```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty