I have been given a question that I have been stuck on for quite a while.
Question:
Given a sorted array of N integers, divide the array in to a maximum of R adjacent and non-overlapping subarrays with a maximum of M elements, so that we can minimize the difference between the largest and smallest valaue within each subarray.The output should contain the maximum difference within any of the subarrays after minimizing the difference in each of the subarrays.
Example:
N = 7
R = 4
M = 3
Original Array: [1,2,3,3,3,5,6]
Optimal subarrays(1 possible case): [1], [2], [3,3,3],[5,6]
Correct Output: 1
I was thinking of testing every possible value for the minimum difference and testing each value in O(N) time, but this would lead to a runtime more costly than nlogn.
What would be the most time and memory efficient solution to solve this problem?
I suggest using bisection to find the largest difference for which it is possible to divide the array in the desired way.
To test if the division is possible, greedily assign elements to subarrays starting from the left while the constraints are met.
Only start a new subarray when forced (either by the difference getting too large, or by reaching the maximum number of elements allowed in an array).
I believe this greedy assignment should always find a solution if one exists for a particular value of difference.