algorithm - 在给定条件下将人放在 n 个小便池中

Question

我从昨天开始思考这个问题，但无法得到我想要的解决方案。

Question is there are n urinals in a washroom.

Now, we have to assign the urinal to a new person in such a way that each new person selects one of the urinals most distant from those already in use.

我们必须制定一个优化算法，使整个为每个人分配小便器的系统自动化。

我的解决方案:我正在考虑使用递归，它会计算每个获取的小便器与每个点的距离，并分配与所有获取的小便器距离最大的小便器。这个解决方案非常幼稚。

我想不出更好的解决方案。不要求任何代码，只要求方向，以便我可以朝那个方向思考。

Answer 1

不太确定起始条件是什么，但我假设在使用任何小便器之前，第一个 2 将占据最隐蔽的位置(在边缘)。我还假设这是一种模拟形式(否则问题微不足道)，因此人们可以随机离开，进入/离开是连续的(一次 1 个)。

1. 找到最长的空闲空间条纹
2. 如果其中一个/两个都是空闲的，则在开始和结束时获得连续的空闲空间

3. 如果中间的最长连胜是 max(start,end) 的两倍以上，则将新人放在该空间的中间，否则将他放在开始或结束位置，具体取决于哪个空间更大

   我 _ _ _ _ _ 我#前两个访客可能在最隐蔽的位置
   #new guy enters, max distance is 5, 所以我们让他离左边的人2格
   我 _ 我 _ _ 我 #that looks nice
   #another guy enter max distance is 2 所以我们把他放在 1 个空间之外
   我_我我_我
   #一个人决定离开
   _ _ 我我 _ _ 我
   #现在中间有 1 个长度为 2 的间隙，开始是空闲的，长度为 2，所以我们把新人放在开始
   我_我我_我
   #另外两个假期
   _ _ 我 _ _ _ 我
   #next guy comes in and since middle gap length is 3 and start gap length is 2 (so 2*start>middle) 我们把那个人放在开始我 _ 我 _ _ _ 我
   #next guy 有 2 个中间间隙，一个长度为 1，另一个长度为 3，所以我们把他放在第二个间隙的中间
   我_我_我_我
   # 等等