Minimum Difficulty of a Job Schedule

Hard
0/120
profile
Contributed by
3 upvotes
Asked in companies
SAP LabsUber

Problem statement

You are given an array ‘ARR’ and an integer ‘K’, Your task is to split the array into exactly ‘K’ subarrays. You have to find the minimum possible sum of the maximum value of each subarray of ‘ARR’.

Note: Each subarray should contain at least one element.

For example: 
You are given ‘ARR’ = [3, 4, 6, 7, 2] and ‘K’ = 3. Here you can divide the array into the subarrays [3], [4, 6, 7] and [2]. Here the sum of maximum values of all subarrays is 3 + 7 + 2 = 12.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each input contains two space-separated integers ‘N’ and ‘K’, representing the size of the array and the given integer ‘K’.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format: 
For each test print a single integer representing the minimum possible sum of maximum values of ‘K’ subarrays of the given array.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N <= 1000
1 <= K <= N
1 <= |ARR[i]| <= 10^6

Time Limit: 1 sec
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function
Sample Input 1:
2
5 3
3 4 6 7 2
3 3
1 2 3
Sample Output 2:
12
6
Explanation:
For the first test case, ‘ARR’ = [3, 4, 6, 7, 2] and ‘K’ = 3. Here you can divide the array into the subarrays [3], [4, 6, 7] and [2]. Here the sum of maximum values of all subarrays is 3 + 7 + 2 = 12.

For the second test case, ‘ARR’ = [1, 2, 3] and ‘K’ = 3. Here you can only divide the array as [1], [2], and [3]. Here the sum of maximum values of all subarrays in 1 + 2 + 3 = 6.
Sample Input 2:
2
5 1
5 6 8 1 10
4 3
1 1 1 1
Sample Output 2:
10
3
Hint

Try to recurse over every possible solution in the array.

Approaches (3)
Recursive Brute Force

In this approach, we iterate over every position in the array and try to make a subarray till that index and recursively call the function on the rest of the array.

At every position, we know where the array starts from the arguments in the recursive function, so we calculate the maximum from the starting position of the current subarray and the position we are making the cut and add it to the recursive call on the rest of the array. We take the minimum of the places of possible sum and return the minimum sum.
 

We create a recursive function subarraySum(arr, startPos, splitRem), Where arr is the given array, startPos is the starting index of the current subarray, splitRem is the number of remaining splits.

 

Algorithm:

  • In the function subarraySum(arr, startPos, splitRem)
    • If splitRem is 0
      • Return maximum value from index startPos to the last element in array ‘arr’
    • Set currArrMax as the negative infinity
    • Set minSubarraySum as infinity
    • Iterate index from startPos to size of arr - splitRem
      • Set num as arr[index]
      • Set currArrMax as maximum of itself and arr[index].
      • Set minSubarraySum as minimum of subarraySum(arr, index + 1, splitRem - 1)
    • Return minSubarraySum
  • In the given function just return minSubarraySum(arr, 0, k - 1)
Time Complexity

O(N^N), Where N is the size of the array.

 

At each iteration of the recursive call, we are making N different recursive calls. Hence the overall time complexity is O(N^N).

Space Complexity

O(N), Where N is the size of the array.

 

The space complexity of the recursion depth will be O(N).

Code Solution
(100% EXP penalty)
Minimum Difficulty of a Job Schedule
Full screen
Console