Skip to content

Latest commit

 

History

History
184 lines (146 loc) · 6.49 KB

README.md

File metadata and controls

184 lines (146 loc) · 6.49 KB
comments difficulty edit_url tags
true
困难
数据库

3268. 查找重叠的班次 II 🔒

English Version

题目描述

表：EmployeeShifts

+------------------+----------+
| Column Name      | Type     |
+------------------+----------+
| employee_id      | int      |
| start_time       | datetime |
| end_time         | datetime |
+------------------+----------+
(employee_id, start_time) 是此表的唯一主键。
这张表包含员工的排班工作，包括特定日期的开始和结束时间。

编写一个解决方案来为每个员工分析重叠排班。如果两个排班在 同一天 且一个排班的 end_time 比另一个排班的 start_time 更晚 则认为两个排班重叠。

对于 每个员工，计算如下内容：

  1. 任何 给定时间 的 最多重叠 班次数。
  2. 所有重叠班次的 总持续时间，以分钟为单位。

返回结果表以 employee_id 升序 排序。

查询结果格式如下所示。

 

示例：

输入：

EmployeeShifts 表：

+-------------+---------------------+---------------------+
| employee_id | start_time          | end_time            |
+-------------+---------------------+---------------------+
| 1           | 2023-10-01 09:00:00 | 2023-10-01 17:00:00 |
| 1           | 2023-10-01 15:00:00 | 2023-10-01 23:00:00 |
| 1           | 2023-10-01 16:00:00 | 2023-10-02 00:00:00 |
| 2           | 2023-10-01 09:00:00 | 2023-10-01 17:00:00 |
| 2           | 2023-10-01 11:00:00 | 2023-10-01 19:00:00 |
| 3           | 2023-10-01 09:00:00 | 2023-10-01 17:00:00 |
+-------------+---------------------+---------------------+

输出：

+-------------+---------------------------+------------------------+
| employee_id | max_overlapping_shifts    | total_overlap_duration |
+-------------+---------------------------+------------------------+
| 1           | 3                         | 600                    |
| 2           | 2                         | 360                    |
| 3           | 1                         | 0                      |
+-------------+---------------------------+------------------------+

解释：

  • 员工 1 有 3 个排班：
    • 2023-10-01 09:00:00 到 2023-10-01 17:00:00
    • 2023-10-01 15:00:00 到 2023-10-01 23:00:00
    • 2023-10-01 16:00:00 到 2023-10-02 00:00:00
    最大重叠班次数量为 3 (from 16:00 to 17:00)。重叠班次的总持续时间为：第 1 个和第 2 个排班之间的 2 小时 (15:00-17:00) + 第 1 个和第 3 个排班之间的 1 小时 (16:00-17:00) + 第 2 个和第 3 个排班之间的 7 小时 (16:00-23:00)，总共：10 小时 = 600 分钟
  • 员工 2 有 2 个排班：
    • 2023-10-01 09:00:00 到 2023-10-01 17:00:00
    • 2023-10-01 11:00:00 到 2023-10-01 19:00:00
    最大重叠班次数量为 2。重叠班次的总持续时间为 6 小时 (11:00-17:00) = 360 分钟。
  • 员工 3 只有 1 个排班，所以没有重叠。

输出表包含 employee_id，同时重叠排班的最大数量,以及每位员工的重叠班次总持续时间（分钟），以 employee_id 升序排序。

解法

方法一：合并 + 连接

我们可以将所有 employee_id 的 start_time 和 end_time 合并到一起，记录在 T 表中，然后使用 LEAD 函数计算出每个 employee_id 的下一个时间段，记录在 P 表中。

接着，我们可以通过 P 表和 EmployeeShifts 表进行连接，计算出每个 employee_id 的 concurrent_count，即同时存在的时间段数量，记录在 S 表中。

最后，我们可以通过 EmployeeShifts 表和自身进行连接，计算出每个 employee_id 的 total_overlap_duration，即总的重叠时间，记录在 U 表中。

最终，我们可以通过 S 表和 U 表进行连接，计算出每个 employee_id 的 max_overlapping_shifts 和 total_overlap_duration。

相似题目：

MySQL

WITH
    T AS (
        SELECT DISTINCT employee_id, start_time AS st
        FROM EmployeeShifts
        UNION DISTINCT
        SELECT DISTINCT employee_id, end_time AS st
        FROM EmployeeShifts
    ),
    P AS (
        SELECT
            *,
            LEAD(st) OVER (
                PARTITION BY employee_id
                ORDER BY st
            ) AS ed
        FROM T
    ),
    S AS (
        SELECT
            P.*,
            COUNT(1) AS concurrent_count
        FROM
            P
            INNER JOIN EmployeeShifts USING (employee_id)
        WHERE P.st >= EmployeeShifts.start_time AND P.ed <= EmployeeShifts.end_time
        GROUP BY 1, 2, 3
    ),
    U AS (
        SELECT
            t1.employee_id,
            SUM(
                TIMESTAMPDIFF(MINUTE, t2.start_time, LEAST(t1.end_time, t2.end_time))
            ) total_overlap_duration
        FROM
            EmployeeShifts t1
            JOIN EmployeeShifts t2
                ON t1.employee_id = t2.employee_id
                AND t1.start_time < t2.start_time
                AND t1.end_time > t2.start_time
        GROUP BY 1
    )
SELECT
    employee_id,
    MAX(concurrent_count) max_overlapping_shifts,
    IFNULL(AVG(total_overlap_duration), 0) total_overlap_duration
FROM
    S
    LEFT JOIN U USING (employee_id)
GROUP BY 1
ORDER BY 1;