Blocks of Three or More Free Adjacent Concert Seats
The ticketing app lets a group book seats together, so the seat-map service needs every maximal block of consecutive available seats in a row with at least…
- Difficulty: Hard
- Topics: Window Functions
- Dialect: MySQL
- Problem: #96
Problem statement
The ticketing app lets a group book seats together, so the seat-map service needs every maximal block of consecutive available seats in a row with at least three seats. Seats in a row are numbered from 1 with no gaps; a sold or held seat breaks a block, and blocks never continue from one row or section to another.
Return event_id, section, row_label, first_seat, last_seat and seats_free for each block, ordered by event_id, section, row_label, then first_seat.
Tables
Table: seat_map
| Column | Type |
|---|---|
| event_id | int |
| section | varchar |
| row_label | char |
| seat_no | int |
| status | enum(available, sold, held) |
Primary key: event_id, section, row_label, seat_no.
One row per seat of an event's seat map. held seats are locked in someone's cart.
Examples
Example 1
seat_map
| event_id | section | row_label | seat_no | status |
|---|---|---|---|---|
| 1 | Gold | A | 1 | sold |
| 1 | Gold | A | 2 | available |
| 1 | Gold | A | 3 | available |
| 1 | Gold | A | 4 | available |
| 1 | Gold | A | 5 | held |
| 1 | Gold | A | 6 | available |
| 1 | Gold | B | 1 | available |
| 1 | Gold | B | 2 | available |
| 1 | Silver | A | 1 | available |
| 1 | Silver | A | 2 | available |
| 1 | Silver | A | 3 | available |
| 1 | Silver | A | 4 | available |
Output
| event_id | section | row_label | first_seat | last_seat | seats_free |
|---|---|---|---|---|---|
| 1 | Gold | A | 2 | 4 | 3 |
| 1 | Silver | A | 1 | 4 | 4 |
How to solve Blocks of Three or More Free Adjacent Concert Seats
Free seats in a block have consecutive numbers, so this is gaps and islands again, partitioned by the physical row: PARTITION BY event_id, section, row_label. After keeping the available seats, seat_no - ROW_NUMBER() OVER (… ORDER BY seat_no) is constant inside a block and jumps after every sold or held seat, because a skipped seat number raises seat_no without raising the row number. Grouping by that key gives each block's first and last seat and its size; HAVING COUNT(*) >= 3 keeps the bookable ones.
In the example, Gold A has free seats 2–4 and 6: the block 2–4 qualifies, seat 6 alone does not. Gold B has only two seats, and Silver A is free end to end — one block of four, never split into overlapping blocks of three, because the blocks are maximal.
Two alternatives: count the non-free seats seen so far with a running SUM (every free seat between two breaks shares the count), or find block starts and ends with NOT EXISTS and pair each start with the nearest end. The window versions are one sort per row.
Reference solution (MySQL)
WITH free AS (
SELECT event_id, section, row_label, seat_no,
seat_no - ROW_NUMBER() OVER (PARTITION BY event_id, section, row_label ORDER BY seat_no) AS block_key
FROM seat_map
WHERE status = 'available'
)
SELECT event_id, section, row_label, MIN(seat_no) AS first_seat, MAX(seat_no) AS last_seat, COUNT(*) AS seats_free
FROM free
GROUP BY event_id, section, row_label, block_key
HAVING COUNT(*) >= 3
ORDER BY event_id, section, row_label, first_seatAnother way
WITH free AS (SELECT event_id, section, row_label, seat_no FROM seat_map WHERE status = 'available'),
starts AS (
SELECT f.* FROM free f WHERE NOT EXISTS (SELECT 1 FROM free p WHERE p.event_id = f.event_id AND p.section = f.section AND p.row_label = f.row_label AND p.seat_no = f.seat_no - 1)
),
ends AS (
SELECT f.* FROM free f WHERE NOT EXISTS (SELECT 1 FROM free n WHERE n.event_id = f.event_id AND n.section = f.section AND n.row_label = f.row_label AND n.seat_no = f.seat_no + 1)
)
SELECT s.event_id, s.section, s.row_label, s.seat_no AS first_seat, MIN(e.seat_no) AS last_seat, MIN(e.seat_no) - s.seat_no + 1 AS seats_free
FROM starts s
JOIN ends e ON e.event_id = s.event_id AND e.section = s.section AND e.row_label = s.row_label AND e.seat_no >= s.seat_no
GROUP BY s.event_id, s.section, s.row_label, s.seat_no
HAVING MIN(e.seat_no) - s.seat_no + 1 >= 3
ORDER BY s.event_id, s.section, s.row_label, first_seatAnother way
WITH marked AS (
SELECT event_id, section, row_label, seat_no, status,
SUM(CASE WHEN status = 'available' THEN 0 ELSE 1 END) OVER (PARTITION BY event_id, section, row_label ORDER BY seat_no ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS breaks
FROM seat_map
)
SELECT event_id, section, row_label, MIN(seat_no) AS first_seat, MAX(seat_no) AS last_seat, COUNT(*) AS seats_free
FROM marked WHERE status = 'available'
GROUP BY event_id, section, row_label, breaks
HAVING COUNT(*) >= 3
ORDER BY event_id, section, row_label, first_seat← Donor Retention by First-Gift Year · Auditorium Bookings That Clash Once Changeover Is Counted →