Description

Table: Cinema

Column NameType
seat_idint
freebool
  • seat_id is an auto-increment column for this table.
  • Each row of this table indicates whether the ith seat is free or not. 1 means free while 0 means occupied.

Problem Statement

Find all the consecutive available seats in the cinema.

Return the result table ordered by seat_id in ascending order. The test cases are generated so that more than two seats are consecutively available.

The result format is in the following example.

Example 1:

Input:

  • Cinema table:
seat_idfree
11
20
31
41
51

Output:

seat_id
3
4
5

Solution

In this problem, you need to find those seats which have at least two consecutive seats free. This problem is similar to Human Traffic of Stadium Problem. You need to filter the rows for which free = 1 and then find consecutive ids.

  1. Find rows where free = 1.
1SELECT seat_id
2    FROM Cinema
3    WHERE free = 1;
  1. Find previous and next available seat_ids.
1SELECT seat_id,
2    LAG(seat_id, 1) OVER (ORDER BY seat_id) AS previous_seat_id,
3    LEAD(seat_id, 1) OVER (ORDER BY seat_id) AS next_seat_id
4    FROM Cinema
5    WHERE free = 1;
  1. Output rows where the difference between seat_id and previous_seat_id is 1 or the difference between seat_id and next_seat_id is 1. This will ensure that the ids are consecutive ids.
1SELECT seat_id 
2    FROM free_seats
3    WHERE (seat_id - previous_seat_id = 1 OR next_seat_id - seat_id = 1);

The final solution would look like this.

1WITH free_seats AS (
2    SELECT seat_id,
3        LAG(seat_id, 1) OVER (ORDER BY seat_id) AS previous_seat_id,
4        LEAD(seat_id, 1) OVER (ORDER BY seat_id) AS next_seat_id
5        FROM Cinema
6        WHERE free = 1
7) SELECT seat_id 
8    FROM free_seats
9    WHERE (seat_id - previous_seat_id = 1 OR next_seat_id - seat_id = 1);