跳转至

3140. 连续空余座位 II 🔒

题目描述

表:Cinema

+-------------+------+
| Column Name | Type |
+-------------+------+
| seat_id     | int  |
| free        | bool |
+-------------+------+
seat_id 是这张表中的自增列。
这张表的每一行表示第 i 个作为是否空余。1 表示空余,而 0 表示被占用。

编写一个解决方案来找到电影院中 最长的空余座位长度

注意:

  • 保证 最多有一个 最长连续序列。
  • 如果有 多个 相同长度 的连续序列,将它们全部输出。

返回结果表以 first_seat_id 升序排序

结果表的格式如下所示。

 

示例:

输入:

Cinema 表:

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

输出:

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

解释:

  • 可用座位的最长连续序列从座位 3 开始,到座位 5 结束,长度为 3。
输出表以 first_seat_id 升序排序。

解法

方法一:使用窗口函数

我们首先找到所有空闲座位,然后将座位进行分组,分组的依据是座位的编号减去它的排名。这样一来,连续的空闲座位将会被分到同一组。接着我们找到每组中的最小座位编号、最大座位编号和连续座位的长度。最后我们找到连续座位长度最大的组,输出这个组的最小座位编号、最大座位编号和连续座位的长度。

 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;

评论