algorithm - How to load balance n servers with following constraints? -

this 1 of interview questions asked me in campus placements.

there 'n' servers assigned load(in integer). have find out min. time required balance them such each server has load 1 on it.

each server can share load adjacent neighbors(left , right).

total load on servers add n.

ex. n=10
initially, 0,0,10,0,0,0,0,0,0,0
time 1 : 0,1,8,1,0,0,0,0,0,0
time 2 : 1,1,6,1,1,0,0,0,0,0
.
.
time 7 : 1,1,1,1,1,1,1,1,1,1

answer 7.

initially, load on servers can present in fashion. not necessary present on 1 server in our current example.

how solve it? couldn't come approach.

thanks in advance

i'm assuming sum of load no more number of servers. approach using binary search on time , complexity o(n * logn).

say, i'm going check if possible balance load in time t. , i'll prefer distribute loads of server s among it's left ones first. if not possible distribute load it's left (because maybe take more time t distribute loads left or maybe of servers occupied), i'm going chose servers on it's right side. if possible distribute load within time t then, i'm going chose smaller t on next iteration, otherwise higher (a.k.a. binary search).

bool isbalancablewithin(time t, load[] loads) {     int lastoccupiedindex = -1;     foreach (index, loads) {         int startindex = max(lastoccupiedindex + 1, index - t);         int endindex   = startindex + loads[i] - 1;          if (endindex > index + t || endindex >= loads.length) return false;          lastoccupiedindex = endindex;     }      return true; }  time lowerbound(load[] loads) {     time lowest  = 0;     time highest = loads.length;      while (lowest <= highest) {         time mid = (lowest + highest) / 2;          if (isbalancablewithin(mid, loads)) highest = mid - 1;         else lowest = mid + 1;     }      return lowest; }