Double-Booked Self-Drive Rental Cars — SQL Joins Problem
A self-drive car rental app found that a sync bug let two customers book the same car for overlapping times.
- Difficulty: Hard
- Topics: Joins, Dates
- Dialect: MySQL
- Problem: #321
Problem statement
A self-drive car rental app found that a sync bug let two customers book the same car for overlapping times. Two confirmed bookings of one car overlap when each starts before the other ends; a booking that starts exactly when another ends is a clean handover, not an overlap. Cancelled bookings never clash.
Return every clashing pair once, with vehicle_id, booking_a and booking_b (the two booking ids, booking_a < booking_b) and overlap_minutes (the length of the shared time). Order by vehicle_id, booking_a, booking_b.
Tables
Table: RentalBooking
| Column | Type |
|---|---|
| booking_id | int |
| vehicle_id | int |
| customer_id | int |
| start_at | datetime |
| end_at | datetime |
| status | enum(confirmed, cancelled) |
Primary key: booking_id.
end_at is always after start_at.
Examples
Example 1
RentalBooking
| booking_id | vehicle_id | customer_id | start_at | end_at | status |
|---|---|---|---|---|---|
| 1 | 50 | 901 | 2024-12-20 09:00:00 | 2024-12-20 18:00:00 | confirmed |
| 2 | 50 | 902 | 2024-12-20 15:00:00 | 2024-12-21 10:00:00 | confirmed |
| 3 | 50 | 903 | 2024-12-21 10:00:00 | 2024-12-21 20:00:00 | confirmed |
| 4 | 51 | 904 | 2024-12-20 08:00:00 | 2024-12-22 08:00:00 | confirmed |
| 5 | 51 | 905 | 2024-12-21 12:00:00 | 2024-12-21 14:30:00 | confirmed |
| 6 | 51 | 906 | 2024-12-21 13:00:00 | 2024-12-21 16:00:00 | cancelled |
| 7 | 52 | 907 | 2024-12-20 10:00:00 | 2024-12-20 12:00:00 | confirmed |
Output
| vehicle_id | booking_a | booking_b | overlap_minutes |
|---|---|---|---|
| 50 | 1 | 2 | 180 |
| 51 | 4 | 5 | 150 |
How to solve Double-Booked Self-Drive Rental Cars
Overlap questions pair rows of one table, so join RentalBooking to itself on the same vehicle_id. The condition a.booking_id < b.booking_id does double duty: it never pairs a booking with itself and it reports each clashing pair once instead of twice.
The overlap test is the one to remember: intervals [s1, e1) and [s2, e2) overlap exactly when s1 < e2 AND s2 < e1. It covers every shape — partial overlap, one booking inside another, identical times — and the strict < makes a handover (one ends at 10:00, the next starts at 10:00) not a clash. The negated form NOT (e1 <= s2 OR e2 <= s1) says "neither is entirely before the other", which is the same thing.
The shared stretch starts at the later of the two starts and ends at the earlier of the two ends: GREATEST(start…) and LEAST(end…), or the equivalent CASE expressions, measured with TIMESTAMPDIFF(MINUTE, …). Both status filters must be applied to both sides. The self join is quadratic per car; sorting each car's bookings by start and comparing neighbours would scale better for large fleets.
Reference solution (MySQL)
SELECT a.vehicle_id, a.booking_id AS booking_a, b.booking_id AS booking_b,
TIMESTAMPDIFF(MINUTE, GREATEST(a.start_at, b.start_at), LEAST(a.end_at, b.end_at)) AS overlap_minutes
FROM RentalBooking a
JOIN RentalBooking b
ON b.vehicle_id = a.vehicle_id
AND a.booking_id < b.booking_id
AND a.start_at < b.end_at
AND b.start_at < a.end_at
WHERE a.status = 'confirmed' AND b.status = 'confirmed'
ORDER BY a.vehicle_id, booking_a, booking_bAnother way
WITH c AS (SELECT booking_id, vehicle_id, start_at, end_at FROM RentalBooking WHERE status <> 'cancelled')
SELECT a.vehicle_id, a.booking_id AS booking_a, b.booking_id AS booking_b,
TIMESTAMPDIFF(MINUTE,
CASE WHEN a.start_at > b.start_at THEN a.start_at ELSE b.start_at END,
CASE WHEN a.end_at < b.end_at THEN a.end_at ELSE b.end_at END) AS overlap_minutes
FROM c a CROSS JOIN c b
WHERE a.vehicle_id = b.vehicle_id AND a.booking_id < b.booking_id
AND NOT (a.end_at <= b.start_at OR b.end_at <= a.start_at)
ORDER BY a.vehicle_id, a.booking_id, b.booking_id← Parcel Delivery Funnel and First-Attempt Rate by City · Daily Sorting-Hub Backlog Including Days With None →