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。

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

解法

方法一

MySQL

评论