Ranked Curbside Rendezvous
Kth smallest cross-label meeting score from position and ready-time arrays
A ride-sharing app is testing when pairs of vehicles could rendezvous along one straight road.
Vehicle i starts at coordinate positions[i] and cannot move before time ready[i]. From that time onward, it may move in either direction at speed at most one coordinate unit per time unit, and it may wait. Coordinates and time are continuous. Each vehicle also belongs to fleet fleets[i].
Only pairs from different fleets are considered. For each unordered pair of distinct vehicles, its rendezvous time is the earliest time at which both vehicles could occupy the same coordinate. Each pair is considered independently; vehicles are not reserved or assigned to other pairs.
Define a pair's score as twice its earliest rendezvous time. This score is always an integer under the given inputs.
Put the scores of all eligible pairs in nondecreasing order, keeping duplicate scores once for every pair that produces them. Return the score at the 1-based rank k.
At least k eligible pairs are guaranteed to exist.
Examples
Example 1
Input: positions = [0,4,10], ready = [0,0,0], fleets = [0,1,2], k = 2 Output: 6
The vehicles at coordinates 0 and 4 can meet at time 2. The pairs involving the vehicle at coordinate 10 can first meet at times 5 and 3. All three pairs are eligible, so the requested rank is taken from those three doubled times.
Example 2
Input: positions = [-2,8,3], ready = [0,0,4], fleets = [7,7,9], k = 1 Output: 9
The first two vehicles belong to the same fleet, so their pair is excluded. The vehicle at coordinate 3 cannot move before time 4, which affects both of its eligible rendezvous times.
Example 3
Input: positions = [5,5,5,5], ready = [0,2,2,6], fleets = [0,1,2,0], k = 3 Output: 4
All vehicles share a starting coordinate. Each eligible pair can meet as soon as both vehicles are ready. Equal scores still occupy separate ranks.
Constraints
- 2 <= len(positions) <= 5000
- len(ready) == len(fleets) == len(positions)
- -1000000 <= positions[i] <= 1000000
- 0 <= ready[i] <= 1000000
- 0 <= fleets[i] <= 1000000
- At least two distinct fleet IDs occur.
- 1 <= k <= the number of unordered pairs whose fleet IDs differ
The intended complexity is O(n log n + n log C) time and O(n) auxiliary space, where C is an upper bound on the answer. At a doubled time S, only vehicles with 2 * ready[i] <= S participate. Their doubled interval endpoints are 2 * (positions[i] + ready[i]) - S and 2 * (positions[i] - ready[i]) + S. Endpoint equality means the intervals intersect, so only strict endpoint separation is subtracted.
Hints
Show hint 1Hint 1
At a candidate time t, an already-ready vehicle can reach every point in the closed interval [positions[i] - (t - ready[i]), positions[i] + (t - ready[i])]. Two vehicles can rendezvous by t exactly when their reachable intervals intersect.
Show hint 2Hint 2
Binary search the doubled time. The left endpoints are ordered by positions[i] + ready[i], and the right endpoints by positions[i] - ready[i], independently of the candidate time. Use two pointers to count strictly disjoint eligible interval pairs, then subtract them from all cross-fleet pairs.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the earliest rendezvous time itself without losing half-unit precision?
- If every vehicle had its own speed, which parts of the endpoint-ordering argument would stop working?
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