Skip to content

3140. Consecutive Available Seats II πŸ”’

Description

Table: Cinema

+-------------+------+
| Column Name | Type |
+-------------+------+
| seat_id     | int  |
| free        | bool |
+-------------+------+
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.

Write a solution to find the length of longest consecutive sequence of available seats in the cinema.

Note:

  • There will always be at most one longest consecutive sequence.
  • If there are multiple consecutive sequences with the same length, include all of them in the output.

Return the result table ordered by first_seat_id in ascending order.

The result format is in the following example.

 

Example:

Input:

Cinema table:

+---------+------+
| seat_id | free |
+---------+------+
| 1       | 1    |
| 2       | 0    |
| 3       | 1    |
| 4       | 1    |
| 5       | 1    |
+---------+------+

Output:

+-----------------+----------------+-----------------------+
| first_seat_id   | last_seat_id   | consecutive_seats_len |
+-----------------+----------------+-----------------------+
| 3               | 5              | 3                     |
+-----------------+----------------+-----------------------+

Explanation:

  • Longest consecutive sequence of available seats starts from seat 3 and ends at seat 5 with a length of 3.
Output table is ordered by first_seat_id in ascending order.

Solutions

Solution 1: Using Window Function

First, we find all the vacant seats, and then group the seats. The grouping is based on the seat number minus its ranking. In this way, consecutive vacant seats will be grouped together. Then we find the minimum seat number, maximum seat number, and length of consecutive seats in each group. Finally, we find the group with the longest length of consecutive seats, and output the minimum seat number, maximum seat number, and length of consecutive seats in this group.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Write your MySQL query statement below
WITH
    T AS (
        SELECT
            *,
            seat_id - (RANK() OVER (ORDER BY seat_id)) AS gid
        FROM Cinema
        WHERE free = 1
    ),
    P AS (
        SELECT
            MIN(seat_id) AS first_seat_id,
            MAX(seat_id) AS last_seat_id,
            COUNT(1) AS consecutive_seats_len,
            RANK() OVER (ORDER BY COUNT(1) DESC) AS rk
        FROM T
        GROUP BY gid
    )
SELECT first_seat_id, last_seat_id, consecutive_seats_len
FROM P
WHERE rk = 1
ORDER BY 1;

Comments