Auditorium Bookings That Clash Once Changeover Is Counted
A city auditorium needs two hours of changeover after every event before the next one may start (stage reset, cleaning, security sweep).
- Difficulty: Hard
- Topics: Joins, Dates
- Dialect: MySQL
- Problem: #97
Problem statement
A city auditorium needs two hours of changeover after every event before the next one may start (stage reset, cleaning, security sweep). Two confirmed bookings of the same venue clash when one starts before the other's end time plus two hours, in either direction. A booking that starts exactly two hours after another ends does not clash. Cancelled bookings never clash.
Return every clashing pair once, as venue, first_booking and second_booking with first_booking < second_booking (booking ids), ordered by venue, first_booking, then second_booking.
Tables
Table: venue_bookings
| Column | Type |
|---|---|
| booking_id | int |
| venue | varchar |
| organiser | varchar |
| starts_at | datetime |
| ends_at | datetime |
| status | enum(confirmed, cancelled) |
Primary key: booking_id.
One row per booking request; ends_at is always after starts_at. Times are on the quarter hour.
Examples
Example 1
venue_bookings
| booking_id | venue | organiser | starts_at | ends_at | status |
|---|---|---|---|---|---|
| 1 | Town Hall | Rotary Club | 2025-06-07 10:00:00 | 2025-06-07 13:00:00 | confirmed |
| 2 | Town Hall | Kala Kendra | 2025-06-07 15:00:00 | 2025-06-07 18:00:00 | confirmed |
| 3 | Town Hall | Lions Club | 2025-06-07 19:30:00 | 2025-06-07 22:00:00 | confirmed |
| 4 | Town Hall | Youth Wing | 2025-06-07 12:00:00 | 2025-06-07 14:00:00 | cancelled |
| 5 | Rangashankara | Theatre Guild | 2025-06-07 09:00:00 | 2025-06-07 23:00:00 | confirmed |
| 6 | Rangashankara | Dance Academy | 2025-06-07 11:00:00 | 2025-06-07 12:30:00 | confirmed |
| 7 | Rangashankara | Music Circle | 2025-06-08 00:30:00 | 2025-06-08 02:00:00 | confirmed |
Output
| venue | first_booking | second_booking |
|---|---|---|
| Rangashankara | 5 | 6 |
| Rangashankara | 5 | 7 |
| Town Hall | 2 | 3 |
How to solve Auditorium Bookings That Clash Once Changeover Is Counted
Clash detection is the interval overlap test on a self join. Two time ranges overlap exactly when each starts before the other ends: a.starts_at < b.ends_at AND b.starts_at < a.ends_at. The changeover rule extends every booking's end by two hours, so the ends become DATE_ADD(…, INTERVAL 2 HOUR). The strict < makes a start exactly at end + 2 h legal — Town Hall bookings 1 (ends 13:00) and 2 (starts 15:00) do not clash, while 2 (ends 18:00) and 3 (starts 19:30) do.
The extended end can cross midnight, which is why the Rangashankara booking at 00:30 the next day clashes with the one ending at 23:00 — comparing full datetimes rather than times of day handles that. Cancelled bookings are filtered on both sides, and a.booking_id < b.booking_id emits each unordered pair once.
The first alternative states the same inequalities in minutes with TIMESTAMPDIFF. The second orders each pair by start time instead — the later one must start before the earlier one's extended end — and then names the pair by LEAST/GREATEST of the ids. The self join is quadratic per venue; real calendars sort by start and compare neighbours, but every clashing pair is still output.
Reference solution (MySQL)
SELECT a.venue, a.booking_id AS first_booking, b.booking_id AS second_booking
FROM venue_bookings a
JOIN venue_bookings b
ON b.venue = a.venue
AND a.booking_id < b.booking_id
AND a.starts_at < DATE_ADD(b.ends_at, INTERVAL 2 HOUR)
AND b.starts_at < DATE_ADD(a.ends_at, INTERVAL 2 HOUR)
WHERE a.status = 'confirmed' AND b.status = 'confirmed'
ORDER BY a.venue, first_booking, second_bookingAnother way
SELECT a.venue, a.booking_id AS first_booking, b.booking_id AS second_booking
FROM venue_bookings a, venue_bookings b
WHERE a.venue = b.venue AND a.booking_id < b.booking_id
AND a.status = 'confirmed' AND b.status = 'confirmed'
AND TIMESTAMPDIFF(MINUTE, b.ends_at, a.starts_at) < 120
AND TIMESTAMPDIFF(MINUTE, a.ends_at, b.starts_at) < 120
ORDER BY a.venue, first_booking, second_bookingAnother way
SELECT a.venue, LEAST(a.booking_id, b.booking_id) AS first_booking, GREATEST(a.booking_id, b.booking_id) AS second_booking
FROM venue_bookings a
JOIN venue_bookings b ON b.venue = a.venue AND b.booking_id <> a.booking_id
WHERE a.status = 'confirmed' AND b.status = 'confirmed'
AND a.starts_at <= b.starts_at
AND b.starts_at < DATE_ADD(a.ends_at, INTERVAL 2 HOUR)
AND (a.starts_at < b.starts_at OR a.booking_id < b.booking_id)
ORDER BY a.venue, first_booking, second_booking← Blocks of Three or More Free Adjacent Concert Seats · Prepaid High-Value Orders Awaiting Dispatch →