打车公司一题求解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

打车公司一题求解

打车公司一题求解# JobHunting - 待字闺中

m*e2017-06-08 07:06

1 楼

设计一个司机和乘客的mapping 系统，一个m*n的二维数组，有很多司机和乘客（乘客
远多于司机），int【x,y]代表所处的坐标，任务是给设计算法，保证每个司机都拉到
一个乘客，并且所有的pickup话费的路程和最小

o*r2017-06-08 07:06

2 楼

二维比较难想，可以先想想一维的情况。这题也可能和二分图有关。我下班后试试。
我擦，匈牙利算法早忘光光了，只记得dfs, 囧。。。
class Location {
Location(int x, int y) {
this.x = x;
this.y = y;
}
public int hashCode() {
return x | y;
}
public boolean equals(Object obj) {
if (obj == null) return false;
else {
if (obj instanceof Location) {
Location l = (Location)obj;
return l.x == x && l.y == y;
} else {
return false;
}
}
}
public int distance(Location location) {
if (location == null) throw new IllegalArgumentException();
return Math.abs(x - location.x) + Math.abs(y - location.y);
}
int x;
int y;
}
class Pair {
final Location left;
final Location right;
Pair(Location left, Location right) {
this.left = left;
this.right = right;
}
public int hashCode() {
return left.hashCode() ^ right.hashCode();
}
public boolean equals(Object obj) {
if (obj == null) return false;
else {
if (obj instanceof Pair) {
Pair p = (Pair)obj;
return p.left == left && p.right == right;
} else {
return false;
}
}
}
}
public class Solution {
public Map minCostPair(Set drivers, Set<
Location> passengers) {
if (drivers == null || passengers == null || drivers.size() == 0 ||
drivers.size() > passengers.size())
throw new IllegalArgumentException();
minCost(drivers, passengers);
return map;
}
private int minCost(Set drivers, Set passengers) {
if (drivers.size() == 1) {
Location d = drivers.iterator().next();
int cost = Integer.MAX_VALUE;
Location passenger = null;
for (Location p : passengers) {
if (d.distance(p) < cost) {
cost = d.distance(p);
passenger = p;
}
}
Pair p = new Pair(d, passenger);
map.put(p, cost);
return cost;
} else {
Location d = drivers.iterator().next();
drivers.remove(d);
int cost = Integer.MAX_VALUE;
for (Location p : passengers) {
map.clear();
Set tmp = new HashSet<>(passengers);
tmp.remove(p);
int c = d.distance(p) + minCost(drivers, tmp);
if (c < cost) {
cost = c;
Pair pair = new Pair(d, p);
map.put(pair, cost);
}
}
return cost;
}
}
private Map map = new HashMap<>();
}