Optimize Driver Repositioning for Minimal Pickup Time
Company: Lyft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Design and implement algorithms for ride-sharing dispatch and capacity planning.
##### Question
Given historical rider demand density and current driver GPS locations, design an algorithm to reposition drivers in real time to minimize expected pickup time across the city. Given N ride requests defined by start and end timestamps, return the minimum number of drivers required so all rides are served without overlap.
##### Hints
Discuss greedy vs. optimization approaches, spatial indexing (k-d tree, grid), and complexity; for the second problem think sweep-line or min-heap.
Quick Answer: This question evaluates spatial algorithms and real-time optimization for ride dispatch together with interval scheduling and capacity planning competencies, covering skills in computational geometry, routing, demand forecasting, and temporal overlap reasoning.
You are given N ride requests as a list of intervals requests, where each request is [start, end] with integer times. A driver can serve at most one ride at a time. Rides use half-open intervals [start, end), so a ride starting at time t does not overlap with a ride ending at time t. Return the minimum number of drivers required so that all rides can be served without overlap.
Constraints
- 0 <= N <= 200000
- requests[i] = [start, end] with integers
- 0 <= start < end <= 10^9
- Intervals are half-open: [start, end)
- Return an integer representing the minimum number of drivers
Solution
import heapq
def min_drivers(requests: list[list[int]]) -> int:
if not requests:
return 0
# Sort by start time
intervals = sorted(requests, key=lambda x: x[0])
# Min-heap of end times for currently assigned drivers
heap = []
max_drivers = 0
for start, end in intervals:
# Free up drivers whose rides ended at or before this start
while heap and heap[0] <= start:
heapq.heappop(heap)
# Assign current ride to a driver (new or reused)
heapq.heappush(heap, end)
if len(heap) > max_drivers:
max_drivers = len(heap)
return max_drivers
Explanation
Sort rides by start time. Maintain a min-heap of end times representing ongoing rides. For each ride, remove all rides from the heap that ended at or before the current start (due to half-open intervals). Then push the current ride's end time. The heap size is the number of concurrent rides (drivers needed) at that moment; the maximum heap size over all iterations is the answer.
Time complexity: O(n log n). Space complexity: O(n).
Hints
- Model the problem as finding the maximum number of overlapping intervals.
- Sort rides by start time and use a min-heap of end times to reuse drivers whose rides have finished.
- When the earliest end time is <= current start, pop it and reuse that driver.
- Alternatively, sort start and end arrays separately and sweep with two pointers.
- Half-open intervals mean end == start does not count as overlap.