跳转至

3401. 寻找环形礼物交换链 🔒

题目描述

表：SecretSanta

+-------------+------+
| Column Name | Type |
+-------------+------+
| giver_id    | int  |
| receiver_id | int  |
| gift_value  | int  |
+-------------+------+
(giver_id, receiver_id) 是这张表的唯一主键。
每一行表示两个员工之间的一次礼物交换记录，giver_id 表示给予礼物的员工，receiver_id 表示收到礼物的员工，gift_value 表示所给予礼物的价值。

编写一个解决方案来找到 总礼物价值 以及 环形礼物交换链的长度：

环形链 被定义为一系列交换，其中：

  • 每位员工都正好向另 一位 员工赠送一份礼物。
  • 每位员工都正好从另 一位 员工那里收到一份礼物。
  • 交换形成一个连续的循环（即 员工 A 给 B 一份礼物，B 给 C，C 再给 A）。

返回结果以链的长度和总礼物价值 降序 排序。

结果格式如下所示。

 

示例：

输入：

SecretSanta 表：

+----------+-------------+------------+
| giver_id | receiver_id | gift_value |
+----------+-------------+------------+
| 1        | 2           | 20         |
| 2        | 3           | 30         |
| 3        | 1           | 40         |
| 4        | 5           | 25         |
| 5        | 4           | 35         |
+----------+-------------+------------+

输出：

+----------+--------------+------------------+
| chain_id | chain_length | total_gift_value |
+----------+--------------+------------------+
| 1        | 3            | 90               |
| 2        | 2            | 60               |
+----------+--------------+------------------+

解释：

  • 链 1 包含员工 1，2 和 3：
    • 员工 1 给 2 一份礼物，员工 2 给 3 一份礼物，员工 3 给 1 一份礼物。
    • 这个链的总礼物价值 = 20 + 30 + 40 = 90。
  • 链 2 包含员工 4 和 5：
    • 员工 4 给 5 一份礼物，员工 5 给 4 一份礼物。
    • 这个链的总礼物价值 = 25 + 35 = 60。

结果表以链的长度和总礼物价值降序排序。

解法

方法一

思考

每位员工恰好送出并收到一份礼物，交换关系构成若干个互不相交的有向环。若在应用层逐条走边，需要额外的过程逻辑，而本题要求用一条 SQL 查出每条环的长度与礼物价值和。

图的规模由交换记录决定，关键是把同一环上的边归到同一组，并避免把一条环重复输出多次。

因此可用递归 CTE 沿 \(\textit{giver\_id}\to\textit{receiver\_id}\) 前进，以环上最小员工编号作为 \(\textit{chain\_id}\)，再按链聚合长度与 \(\textit{gift\_value}\) 之和，最后按长度与总价值降序排列。

1

评论