Create minimum no of groups of subsequent elements with max diff between elements being less than k-CodePudding

Create minimum no of groups of subsequent elements with max diff between elments being less than k

Constraints:

0 < A[i] < MAX_INT
Number of elements: 1 < N < 10^6

Input

N = 11
A = [1,2,4,10,5,4,11,21,15,5,1]
K = 11

Output

[ [1,2,4,10,5,4,11], [21,15], [5,1] ]

Explanation:

Group 1: min = 1, max = 11 -> diff = 10, can't include 21 as max diff between this group will become 21-1 = 20, it shouldn't exceed 10 

Group 2: min = 15, max = 21 -> diff = 6 => 6 < k can't include 5 as max diff will exceed K

Group 3: min = 1, max = 5 -> diff = 4 => 4 < k

Will greedy algorithm always return correct answer if we start from 1st element and maintain local min,max value and create groups ?

CodePudding user response：

The greedy algorithm is optimal.

Let F(A) be the minimum number of groups the array A can be divided into.

Assume A is 1 based indexed and A[k: j] is the sub array from A[k] to A[j] where k <= j

Clearly

F(A[2:n]) >= F(A[3:n])
F(A[3:n]) >= F(A[4:n])
and so on

So it is optimal for the first group that you select to be as long as possible.