如何使用以下约束对n台服务器进行负载平衡？

Question

这是我在校园中的一个面试问题。

有n个服务器被分配一些负载（整数）。我们必须找出最小值。平衡它们所需的时间，以使每台服务器都有负载1。

每台服务器只能与其相邻的邻居（左侧和右侧）共享其负载。

所有服务器上的总加载总和为n。

Ex。 n = 10
最初，0,0,10,0,0,0,0,0,0,0
时间1：0,1,8,1,0,0,0,0,0， 0
时间2：1,1,6,1,1,0,0,0,0,0
。
。
时间7：1,1,1,1,1,1,1,1,1,1

回答是7.

最初，在服务器上的负载可以存在于任何方式。没有必要只在一台服务器上显示它，因为它在我们当前的示例中。

我该如何解决？我无法想出任何方法。

在此先感谢

Answer 1

我假设负载的总和不超过服务器的数量。我的方法是随着时间的推移使用二分查找，复杂度为O（n * logn）。

说，我要检查是否有可能在时间上平衡负荷t。而且我宁愿首先在它的左边分配一个服务器的负载s。如果不可能将所有负载分配给剩余的负载（因为可能需要更多的时间来将所有负载分配到左边或者其中一些服务器已经被占用），那么我将选择它的右侧是服务器。如果有可能在时间内分配所有负载，则在下一次迭代中我将选择较小的t，否则选择较高的（又名二进制搜索）。

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个时间段。其中一项工作需要向右移动，需要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。