Double-Booked Beds in a Co-Living Space — SQL Joins Problem
A co-living operator's old booking tool allowed two residents to be booked on the same bed for overlapping dates.
- Difficulty: Hard
- Topics: Joins, Dates
- Dialect: MySQL
- Problem: #369
Problem statement
A co-living operator's old booking tool allowed two residents to be booked on the same bed for overlapping dates. A booking occupies the nights from move_in up to the day before move_out — so one resident moving out on the day another moves in is not a clash.
Return every pair of bookings on the same bed whose nights overlap, with bed_code, first_booking and second_booking (the smaller and larger booking_id) and overlap_nights (the number of nights both hold). Order by bed_code, first_booking, second_booking.
Tables
Table: BedBooking
| Column | Type |
|---|---|
| booking_id | int |
| bed_code | varchar |
| resident | varchar |
| move_in | date |
| move_out | date |
Primary key: booking_id.
move_out is the departure day and is always after move_in. bed_code is the room and bed, such as KOR-204-B.
Examples
Example 1
BedBooking
| booking_id | bed_code | resident | move_in | move_out |
|---|---|---|---|---|
| 1 | KOR-204-A | Aisha Khan | 2025-04-01 | 2025-06-01 |
| 2 | KOR-204-A | Diya Nair | 2025-06-01 | 2025-08-01 |
| 3 | KOR-204-B | Arjun Rao | 2025-04-10 | 2025-05-10 |
| 4 | KOR-204-B | Kabir Das | 2025-05-01 | 2025-07-01 |
| 5 | KOR-204-B | Liam Iyer | 2025-05-05 | 2025-05-20 |
| 6 | KOR-301-A | Meera Shah | 2025-04-15 | 2025-09-15 |
| 7 | KOR-301-A | Zara Joshi | 2025-06-01 | 2025-06-02 |
Output
| bed_code | first_booking | second_booking | overlap_nights |
|---|---|---|---|
| KOR-204-B | 3 | 4 | 9 |
| KOR-204-B | 3 | 5 | 5 |
| KOR-204-B | 4 | 5 | 15 |
| KOR-301-A | 6 | 7 | 1 |
How to solve Double-Booked Beds in a Co-Living Space
Overlap is a property of a pair of rows, so self join BedBooking on the bed. a.booking_id < b.booking_id keeps every pair once (and never pairs a booking with itself). A booking holds the half-open range of nights [move_in, move_out), and two half-open ranges overlap exactly when each starts before the other ends: a.move_in < b.move_out AND b.move_in < a.move_out. Strict inequalities make back-to-back stays — Aisha leaving on 1 June as Diya arrives — a non-clash.
The overlap itself runs from the later start, GREATEST(move_in), to the earlier end, LEAST(move_out), and DATEDIFF counts the nights between. Zara's one-night stay inside Meera's long one overlaps for 1 night. On bed KOR-204-B three bookings collide: 3 and 4 share 9 nights, 3 and 5 share 5, and 4 and 5 share 15 — every pair is reported, not just neighbours in time.
The alternative computes the overlap for every pair and keeps the positive ones, writing LEAST/GREATEST as CASE. The self join is quadratic per bed, which is fine for a handful of bookings per bed; an index on (bed_code, move_in) helps on a real table.
Reference solution (MySQL)
SELECT a.bed_code,
a.booking_id AS first_booking,
b.booking_id AS second_booking,
DATEDIFF(LEAST(a.move_out, b.move_out), GREATEST(a.move_in, b.move_in)) AS overlap_nights
FROM BedBooking a
JOIN BedBooking b
ON b.bed_code = a.bed_code
AND a.booking_id < b.booking_id
AND a.move_in < b.move_out
AND b.move_in < a.move_out
ORDER BY a.bed_code, first_booking, second_bookingAnother way
SELECT * FROM (SELECT a.bed_code, a.booking_id AS first_booking, b.booking_id AS second_booking, DATEDIFF(CASE WHEN a.move_out < b.move_out THEN a.move_out ELSE b.move_out END, CASE WHEN a.move_in > b.move_in THEN a.move_in ELSE b.move_in END) AS overlap_nights FROM BedBooking a JOIN BedBooking b ON b.bed_code = a.bed_code AND b.booking_id > a.booking_id) p WHERE overlap_nights > 0 ORDER BY bed_code, first_booking, second_booking← Enquiry-to-Token Funnel by Lead Source · Occupied Flats on the First of Each Month →