实现一个迷你优步
- 司机提供他们的位置
- 用户请求，然后返回一个匹配的司机
实现下列函数
-
report(driver_id, lat, lng)- 如果没有找到匹配的trip，返回null
- 否则返回匹配trip信息
-
request(rider_id, lat, lng)- 建立一个trip
- 找到一个最近的司机，标记这个司机为不可用
- 将司机id填入trip
- 返回trip
Java中trip的定义
public class Trip {
public int id; // trip's id, primary key
public int driver_id, rider_id; // foreign key
public double lat, lng; // pick up location
}
思路：Integer to Trip, Integer to Location，一个是用来返回已经有trip的driver， 一个是用来返回没有trip的driver，求最近就是求现有driver的跟rider的最小值；更新两个hashmap即可；
/**
* Definition of Trip:
* public class Trip {
* public int id; // trip's id, primary key
* public int driver_id, rider_id; // foreign key
* public double lat, lng; // pick up location
* public Trip(int rider_id, double lat, double lng);
* }
* Definition of Helper
* class Helper {
* public static double get_distance(double lat1, double lng1,
double lat2, double lng2) {
* // return distance between (lat1, lng1) and (lat2, lng2)
* }
* };
*/
public class MiniUber {
private class Location {
public double lat;
public double lng;
public Location(double lat, double lng) {
this.lat = lat;
this.lng = lng;
}
}
private HashMap<Integer, Trip> driver2Trip;
private HashMap<Integer, Location> driver2Location;
public MiniUber() {
driver2Trip = new HashMap<Integer, Trip>();
driver2Location = new HashMap<Integer, Location>();
}
// @param driver_id an integer
// @param lat, lng driver's location
// return matched trip information if there have matched rider or null
public Trip report(int driver_id, double lat, double lng) {
if(driver2Trip.containsKey(driver_id)) {
return driver2Trip.get(driver_id);
} else {
// update location hashmap;
if(driver2Location.containsKey(driver_id)) {
driver2Location.get(driver_id).lat = lat;
driver2Location.get(driver_id).lng = lng;
} else {
driver2Location.put(driver_id, new Location(lat, lng));
}
// return null trip info;
return null;
}
}
// @param rider_id an integer
// @param lat, lng rider's location
// return a trip
public Trip request(int rider_id, double lat, double lng) {
Trip trip = new Trip(rider_id, lat, lng);
double distance = -1;
int driver_id = -1;
for(Integer driver: driver2Location.keySet()) {
Location location = driver2Location.get(driver);
double dis = Helper.get_distance(lat, lng, location.lat, location.lng);
if(distance == -1 || dis < distance) {
distance = dis;
driver_id = driver;
}
}
if(driver_id != -1) {
driver2Location.remove(driver_id);
}
trip.driver_id = driver_id;
driver2Trip.put(driver_id, trip);
return trip;
}
}