Uber: Fleet Vehicles on Two Drivers' Shifts at Once
Fleet partners rent their cars to Uber drivers shift by shift.
- Difficulty: Hard
- Topics: Joins, Dates, Conditional Logic
- Dialect: MySQL
- Problem: #991
Problem statement
Fleet partners rent their cars to Uber drivers shift by shift. A car can only be driven by one person at a time, so two different drivers holding the same car at the same moment means a booking error — or an unregistered driver. The fleet-compliance team pulled the shift log at 2024-10-21 00:00:00 and wants every conflict.
Ignore cancelled shifts. A shift with a NULL end_at is still running and counts as lasting until 2024-10-21 00:00:00. Two shifts conflict when they are on the same vehicle, belong to different drivers and overlap for a positive length of time — a shift ending at the exact moment another starts is not a conflict. Return each conflicting pair once as plate, first_shift (the smaller shift_id), second_shift and overlap_minutes (whole minutes during which both shifts were running), ordered by plate, first_shift, second_shift.
A practice scenario set at Uber: the tables and data are invented, and this is not a question from, or endorsed by, Uber.
Tables
Table: Vehicle
| Column | Type |
|---|---|
| vehicle_id | int |
| plate | varchar |
Primary key: vehicle_id.
One row per fleet car; plates are upper-case.
Table: VehicleShift
| Column | Type |
|---|---|
| shift_id | int |
| vehicle_id | int |
| driver_id | int |
| start_at | datetime |
| end_at | datetime |
| status | enum(completed, active, cancelled) |
Primary key: shift_id.
One row per shift a driver booked on a car. end_at is NULL only for an active shift; every shift starts before the log was pulled.
Examples
Example 1
Vehicle
| vehicle_id | plate |
|---|---|
| 1 | MH12AB1234 |
| 2 | MH14CD5678 |
| 3 | KA01EF9012 |
VehicleShift
| shift_id | vehicle_id | driver_id | start_at | end_at | status |
|---|---|---|---|---|---|
| 1 | 1 | 11 | 2024-10-20 06:00:00 | 2024-10-20 14:00:00 | completed |
| 2 | 1 | 12 | 2024-10-20 13:30:00 | 2024-10-20 21:30:00 | completed |
| 3 | 1 | 13 | 2024-10-20 21:30:00 | NULL | active |
| 4 | 1 | 14 | 2024-10-20 22:00:00 | 2024-10-20 23:00:00 | completed |
| 5 | 2 | 15 | 2024-10-20 08:00:00 | 2024-10-20 12:00:00 | completed |
| 6 | 2 | 16 | 2024-10-20 09:00:00 | 2024-10-20 10:00:00 | cancelled |
| 7 | 2 | 15 | 2024-10-20 11:00:00 | 2024-10-20 15:00:00 | completed |
| 8 | 3 | 17 | 2024-10-20 07:00:00 | 2024-10-20 09:00:00 | completed |
| 9 | 3 | 18 | 2024-10-20 05:00:00 | 2024-10-20 10:00:00 | completed |
Output
| plate | first_shift | second_shift | overlap_minutes |
|---|---|---|---|
| KA01EF9012 | 8 | 9 | 120 |
| MH12AB1234 | 1 | 2 | 30 |
| MH12AB1234 | 3 | 4 | 60 |
How to solve Uber: Fleet Vehicles on Two Drivers' Shifts at Once
Conflicts are pairs of rows, so the table is joined to itself: a and b are two shifts on the same vehicle. a.shift_id < b.shift_id keeps each unordered pair exactly once and puts the smaller id first, as the output asks, and a.driver_id <> b.driver_id drops a driver's own double-logged shifts, which do not put a second person in the car.
Before pairing, a CTE removes cancelled shifts and closes the open ones: COALESCE(end_at, '2024-10-21 00:00:00') treats a running shift as lasting until the log was pulled. Shift 3, still active, therefore overlaps shift 4 from 22:00 to 23:00.
Two intervals overlap exactly when each starts before the other ends: a.start_at < b.end_at AND b.start_at < a.end_at. This one test covers every arrangement — partial overlap, one shift inside the other (shifts 8 and 9), either one first — and the strict < excludes shifts that only touch, like shift 2 ending at 21:30 and shift 3 starting then. Their shared time runs from the later start to the earlier end, TIMESTAMPDIFF(MINUTE, GREATEST(starts), LEAST(ends)).
The alternative computes the shared interval first with CASE expressions and keeps pairs where it has positive length — the overlap test rewritten as later start < earlier end. A self join is quadratic per vehicle; an index on (vehicle_id, start_at) keeps it to the shifts of one car.
Reference solution (MySQL)
WITH s AS (
SELECT shift_id, vehicle_id, driver_id, start_at, COALESCE(end_at, '2024-10-21 00:00:00') AS end_at
FROM VehicleShift
WHERE status <> 'cancelled'
)
SELECT v.plate, a.shift_id AS first_shift, b.shift_id AS second_shift,
TIMESTAMPDIFF(MINUTE, GREATEST(a.start_at, b.start_at), LEAST(a.end_at, b.end_at)) AS overlap_minutes
FROM s a
JOIN s b
ON b.vehicle_id = a.vehicle_id
AND a.shift_id < b.shift_id
AND a.driver_id <> b.driver_id
AND a.start_at < b.end_at
AND b.start_at < a.end_at
JOIN Vehicle v ON v.vehicle_id = a.vehicle_id
ORDER BY v.plate, first_shift, second_shiftAnother way
SELECT plate, first_shift, second_shift, TIMESTAMPDIFF(MINUTE, from_at, to_at) AS overlap_minutes FROM (
SELECT v.plate, a.shift_id AS first_shift, b.shift_id AS second_shift,
CASE WHEN a.start_at > b.start_at THEN a.start_at ELSE b.start_at END AS from_at,
CASE WHEN IFNULL(a.end_at, '2024-10-21 00:00:00') < IFNULL(b.end_at, '2024-10-21 00:00:00')
THEN IFNULL(a.end_at, '2024-10-21 00:00:00') ELSE IFNULL(b.end_at, '2024-10-21 00:00:00') END AS to_at
FROM VehicleShift a, VehicleShift b, Vehicle v
WHERE a.vehicle_id = b.vehicle_id AND v.vehicle_id = a.vehicle_id
AND a.shift_id < b.shift_id AND a.driver_id <> b.driver_id
AND a.status IN ('completed', 'active') AND b.status IN ('completed', 'active')
) x
WHERE from_at < to_at
ORDER BY plate, first_shift, second_shift← Uber: Back-to-Back Trips Starting in the Last Drop Zone · Uber: Evening Hours Where Requests Outran Online Drivers →