Curbside Dispatch Radius
Minimum maximum absolute difference for one-to-one matching of two arrays
A ride-sharing app is coordinating pickups along one straight road. Each rider and each available driver has an integer position on the road. Positions may be negative, and multiple riders or drivers may share a position.
The app must assign exactly one driver to every rider. Each driver can be assigned to at most one rider, and unused drivers are allowed. There are at least as many drivers as riders.
The pickup distance for an assigned rider and driver is the absolute difference between their positions. A dispatch radius is sufficient if an assignment exists in which every pickup distance is at most that radius.
Given the arrays riders and drivers, return the smallest sufficient dispatch radius. The arrays are not necessarily sorted.
Examples
Example 1
Input: riders = [9,2], drivers = [15,1,8] Output: 1
The rider at position 2 can use the driver at position 1, and the rider at position 9 can use the driver at position 8. The driver at position 15 can remain unused. A radius of zero cannot cover either rider.
Example 2
Input: riders = [0,5,0], drivers = [4,-1,1] Output: 1
The two riders at position 0 need different drivers. Assign the drivers at positions -1 and 1 to them, and assign the driver at position 4 to the rider at position 5. Drivers cannot be reused even when riders share a position.
Example 3
Input: riders = [-7], drivers = [6] Output: 13
The only driver must serve the only rider. Their pickup distance crosses position zero, so both sides of the road contribute to the required radius.
Constraints
- 1 <= riders.length <= drivers.length <= 3000
- -1000000 <= riders[i], drivers[j] <= 1000000
- All positions are integers.
- The input arrays may be unsorted and may contain duplicate positions.
The intended solution takes O(n log n + m log m + (n + m) log C) time, where n and m are the array lengths and C is the coordinate range, and O(n + m) auxiliary space for sorted copies. Only the minimum radius is returned, so multiple optimal assignments do not affect the answer.
Hints
Show hint 1Hint 1
If a radius is sufficient, every larger radius is also sufficient. Can you search for the first sufficient integer radius?
Show hint 2Hint 2
Sort both arrays. For a fixed radius, process riders from left to right, discard drivers that are too far left, and use the earliest remaining driver that can serve the current rider.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return one assignment achieving the minimum radius, using the original input indices?
- How would the feasibility check change if each driver could serve a given number of riders at that driver's position?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem