Double-Booked Hotel Rooms — SQL Joins Problem
A channel-manager glitch let two websites sell the same room for the same nights.
- Difficulty: Medium
- Topics: Joins, Dates
- Dialect: MySQL
- Problem: #538
Problem statement
A channel-manager glitch let two websites sell the same room for the same nights. Two active reservations of the same room overlap when each one starts before the other ends; a stay checking out on the day the next one checks in does not overlap. Cancelled reservations never clash with anything.
Return one row per clashing pair with room_no, first_reservation (the smaller reservation_id), second_reservation (the larger) and overlap_nights (the number of nights both hold). Return the rows in any order.
Tables
Table: RoomReservation
| Column | Type |
|---|---|
| reservation_id | int |
| room_no | int |
| guest_name | varchar |
| check_in | date |
| check_out | date |
| status | enum(active, cancelled) |
Primary key: reservation_id.
One hotel. A reservation holds room_no for the nights from check_in up to (not including) check_out.
Examples
Example 1
RoomReservation
| reservation_id | room_no | guest_name | check_in | check_out | status |
|---|---|---|---|---|---|
| 1 | 204 | Aarav | 2024-12-20 | 2024-12-24 | active |
| 2 | 204 | Diya | 2024-12-22 | 2024-12-26 | active |
| 3 | 204 | Kabir | 2024-12-26 | 2024-12-28 | active |
| 4 | 305 | Meera | 2024-12-21 | 2024-12-23 | active |
| 5 | 305 | Rohan | 2024-12-21 | 2024-12-22 | cancelled |
| 6 | 305 | Zara | 2024-12-18 | 2024-12-25 | active |
| 7 | 204 | Ishaan | 2024-12-23 | 2024-12-27 | active |
Output
| room_no | first_reservation | second_reservation | overlap_nights |
|---|---|---|---|
| 204 | 1 | 2 | 2 |
| 204 | 1 | 7 | 1 |
| 204 | 2 | 7 | 3 |
| 204 | 3 | 7 | 1 |
| 305 | 4 | 6 | 2 |
How to solve Double-Booked Hotel Rooms
Clashes are between two rows of the same table, so the query is a self join of RoomReservation on room_no, restricted to active rows on both sides. Writing a.reservation_id < b.reservation_id does two jobs: it stops a reservation from matching itself, and it keeps each clashing pair once, with the smaller id first as the statement asks.
The overlap test for half-open stays [check_in, check_out) is the classic one: they overlap exactly when a.check_in < b.check_out AND b.check_in < a.check_out. The strict < is what makes back-to-back stays safe — a check-out on the 24th and a check-in on the 24th share no night. It also catches containment (one stay entirely inside another), which a test on just the start dates would miss.
The shared part runs from the later check-in, GREATEST(a.check_in, b.check_in), to the earlier check-out, LEAST(a.check_out, b.check_out), and their DATEDIFF is the number of double-sold nights. The alternative spells LEAST/GREATEST with CASE and uses "the overlap is positive" as the clash test, which is the same condition. Both are quadratic per room; an index on (room_no, check_in) limits the comparisons.
Reference solution (MySQL)
SELECT a.room_no,
a.reservation_id AS first_reservation,
b.reservation_id AS second_reservation,
DATEDIFF(LEAST(a.check_out, b.check_out), GREATEST(a.check_in, b.check_in)) AS overlap_nights
FROM RoomReservation a
JOIN RoomReservation b
ON b.room_no = a.room_no
AND a.reservation_id < b.reservation_id
AND a.check_in < b.check_out
AND b.check_in < a.check_out
WHERE a.status = 'active' AND b.status = 'active'Another way
SELECT a.room_no, a.reservation_id AS first_reservation, b.reservation_id AS second_reservation,
DATEDIFF(CASE WHEN a.check_out < b.check_out THEN a.check_out ELSE b.check_out END,
CASE WHEN a.check_in > b.check_in THEN a.check_in ELSE b.check_in END) AS overlap_nights
FROM RoomReservation a, RoomReservation b
WHERE a.room_no = b.room_no AND a.reservation_id < b.reservation_id
AND a.status = 'active' AND b.status = 'active'
AND DATEDIFF(CASE WHEN a.check_out < b.check_out THEN a.check_out ELSE b.check_out END,
CASE WHEN a.check_in > b.check_in THEN a.check_in ELSE b.check_in END) > 0← Passengers Who Flew a Route in Both Directions · Loyalty Points Expiring for Inactive Members →