How to load balance n servers with the following restrictions?

Question

That was one of the questions I was asked at my campus placements.

There are "n" servers that are assigned with some load (in whole). We have to find out the min. the time required for their balance, so that each server has a load of 1 on it.

Each server can share its load only with its neighboring neighbors (left and right).

The total load on all servers is n.

Ex. n = 10
Initially 0,0,10,0,0,0,0,0,0,0,0,0
Time 1: 0,1,8,1,0,0,0,0,0,0,0
Time 2: 1, 1,6,1,1,0,0,0,0,0,0
.
.
Time 7: 1,1,1,1,1,1,1,1,1,1,1,1

The answer is 7.

Initially, loading on servers can be present in any way. It is not necessary that it is present on only one server, as in our current example.

How do I solve it? I could not come up with any approach.

Thanks in advance

Answer 1

I assume that the amount of load is no more than the number of servers. My approach uses binary search over time, and the complexity is O (n * logn) .

, , t. s . ( , , t, , , ), . t, t , (aka ).

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;
}

Answer 2

, . , 7 , 7 .

,

0, 0, 6, 0, 4, 0, 0, 0, 0, 0

6, . , 4 . , 5 , 4 .

n = 15

0, 0, 0, 3, 0, 0, 0, 0, 4, 0, 0, 6, 2, 0, 0

3 , 3 . 4 , 5 ( , 3). 6 , 4 . 6 , 1 . 2 , 2 . 5, 4 5 .

, O (n) :

int excess = 0;
int answer = 0;
for ( int i = 0; i < N; i++ )
{
    excess = excess + array[i] - 1;
    if ( abs(excess) > answer )
        answer = abs(excess);
}

excess , , , . excess answer.