Dispatch Offer Expirations
HardGreedy · Uber
Ride requests are dispatched one at a time in the order they appear in orders. Each order is [order_id, zone, request_ts]. Each driver is [driver_id, zone, available_ts]; the drivers list is in priority order (index 0 is the highest priority).
An offer for an order stays open until time request_ts + timeout. When an order is dispatched, it goes to the highest-priority driver who:
- has not already been assigned to an earlier order,
- is in the same
zoneas the order, and - has
available_ts <= request_ts + timeout.
That driver is then used up. If no driver qualifies, the order gets "NONE".
Return a list of [order_id, driver_id_or_"NONE"], one per order, in the same order as orders. Note that orders is not necessarily sorted by request_ts.
Example 1
- Input:
- orders = [[101, "sf", 10], [102, "sf", 12], [103, "la", 5]], drivers = [["d1", "sf", 20], ["d2", "sf", 8], ["d3", "sf", 14], ["d4", "la", 9]], timeout = 3
- Output:
- [[101, "d2"], [102, "d3"], [103, "NONE"]]
- Explanation
- Order 101 has deadline 13:
d1(20) is too late, so the highest-priority match isd2. Order 102 has deadline 15:d1is still too late andd2is used, sod3(14) takes it. Order 103 has deadline 8, but the onlyladriver arrives at 9.
Example 2
- Input:
- orders = [[1, "z", 5], [2, "z", 0]], drivers = [["a", "z", 4], ["b", "z", 1]], timeout = 0
- Output:
- [[1, "a"], [2, "NONE"]]
- Explanation
- Order 1 is dispatched first with deadline 5, and
ais the highest-priority qualifying driver even thoughbis available sooner. Order 2 has deadline 0 andb(1) misses it.
Example 3
- Input:
- orders = [[7, "q", 3]], drivers = [["x", "q", 10]], timeout = 7
- Output:
- [[7, "x"]]
- Explanation
- The deadline is 3 + 7 = 10 and the driver is available at exactly 10, which still counts.
Constraints
0 <= orders.length, drivers.length <= 10^5- Order ids are unique integers; driver ids are unique strings
0 <= request_ts, available_ts, timeout <= 10^9