找到计划中最近的交叉点

Question

我最近在采访中被问到以下问题:

假设你在笛卡尔坐标系(Quadrant I)上跟随网格.

o - x - x - x - o
|   |   |   |   |
x - x - x - o - x
|   |   |   |   |
x - o - o - x - x

where,  o => person at intersection  and  x => no person at intersection

class Point {
 int x;
 int y;
 boolean hasPerson;
}


Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {

}

在给定人员位置(点)列表的情况下实施例程,找到最接近所有给定点的位置(点).

你会如何解决这个问题？

1)方法是kd树,但是你知道其他任何解决方案吗？

Answer 1

如果问题要求最小化曼哈顿距离(也就是说,人们只是平行于轴行走),那么问题就非常重要了.首先,选择x坐标和y坐标是独立的问题.

然后,对于每个坐标,只需找到沿该轴的人的位置的中值.对于许多人的配置,可以有不止一个点最小化所有人的步行距离的总和.(只考虑两个人在x和相同的y坐标中分开超过2个区块;两个人之间的任何交叉点都需要两个人相同的总步数.)

如果问题要求最小化欧几里德距离,那么目标是找到2变量L1中值.这是一个标准问题,但它远非微不足道.(例如,请参见此处.)有一个独特的答案.鉴于这是一个面试问题,我怀疑这不适用.