Blocks of Three or More Free Adjacent Concert Seats

Hard
96.

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 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

ColumnTypeValues
event_idint
sectionvarchar
row_labelchar
seat_noint
statusenumavailable, sold, held

Primary key (together): 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.

Example

The rows must come back in the order shown.

seat_map

event_idsectionrow_labelseat_nostatus
1GoldA1sold
1GoldA2available
1GoldA3available
1GoldA4available
1GoldA5held
1GoldA6available
1GoldB1available
1GoldB2available
1SilverA1available
1SilverA2available
2 more rows

Output

event_idsectionrow_labelfirst_seatlast_seatseats_free
1GoldA243
1SilverA144
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
event_idint
sectionvarchar
row_labelchar
seat_noint
statusenum(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_idsectionrow_labelseat_nostatus
1GoldA1sold
1GoldA2available
1GoldA3available
1GoldA4available
1GoldA5held
1GoldA6available
1GoldB1available
1GoldB2available
1SilverA1available
1SilverA2available
1SilverA3available
1SilverA4available

Output

event_idsectionrow_labelfirst_seatlast_seatseats_free
1GoldA243
1SilverA144

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_seat

Another 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_seat

Another 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 →