algorithm - 最小化到最远点的距离

Question

这个问题是在求职面试中被问到的。

Assume you're looking to move, and have a set of amenities that youwant to have easy access to from your new home. You have found aneighborhood you like, each block of which has zero or more amenities.How would you pick the block to live in such that the farthestdistance to any amenity in your list is minimized?

For example, say your list contains {school, grocery}, and the blocksare as follows:

1: restaurant, grocery

2: movie theater

3: school

4:

5: school

The ideal choice would be block 2, such that the distances to thegrocery and the nearest school are 1 each. Living on block 1 or 3would make one of the distances zero, but the other one 2.

我想出了一个简单的解决方案，如下面的伪代码所示:

max = minus infinity
min = plus infinity    

for r in requirements:
  for i in blocks:
    for j in blocks:
      if j.amenities contains r:
        max = maximum {max, dist(i, j)}
    if max < min:
      live_at = i

如果 n 是 block 的数量，则该算法的时间复杂度是 O(n^2)，假设需求列表比 n。我们可以做得更好吗？

This问题似乎很相似，尽管我不清楚答案。它引用了一篇论文，并以“在中心画一个圆，c”开头，但没有任何说明 c 是什么。

Answer 1

是的，我们可以在 O(n*k log n) 中完成，其中 n 是街区的数量，k 是便利设施的数量

设施列表很小，所以创建 ArrayList对于每个便利设施和存在该便利设施的商店街区位置。

即使用您提供的示例:

• A["餐厅"] = {1}
• A["杂货店"] = {1}
• A["电影院"] = {2}
• A["学校"] = {3,5}

所以现在我们可以遍历所有 block 并使用 lower_bound(二进制搜索)为每个需要的便利设施找到具有所需便利设施的最近街区

然后只需选择与所需便利设施距离最短的街区即可。