3401. Find Circular Gift Exchange Chains 🔒
题目描述
Table: SecretSanta
+-------------+------+ | Column Name | Type | +-------------+------+ | giver_id | int | | receiver_id | int | | gift_value | int | +-------------+------+ (giver_id, receiver_id) is the unique key for this table. Each row represents a record of a gift exchange between two employees, giver_id represents the employee who gives a gift, receiver_id represents the employee who receives the gift and gift_value represents the value of the gift given.
Write a solution to find the total gift value and length of circular chains of Secret Santa gift exchanges:
A circular chain is defined as a series of exchanges where:
- Each employee gives a gift to exactly one other employee.
- Each employee receives a gift from exactly one other employee.
- The exchanges form a continuous loop (e.g., employee A gives a gift to B, B gives to C, and C gives back to A).
Return the result ordered by the chain length and total gift value of the chain in descending order.
The result format is in the following example.
Example:
Input:
SecretSanta table:
+----------+-------------+------------+ | giver_id | receiver_id | gift_value | +----------+-------------+------------+ | 1 | 2 | 20 | | 2 | 3 | 30 | | 3 | 1 | 40 | | 4 | 5 | 25 | | 5 | 4 | 35 | +----------+-------------+------------+
Output:
+----------+--------------+------------------+ | chain_id | chain_length | total_gift_value | +----------+--------------+------------------+ | 1 | 3 | 90 | | 2 | 2 | 60 | +----------+--------------+------------------+
Explanation:
- Chain 1 involves employees 1, 2, and 3:
- Employee 1 gives a gift to 2, employee 2 gives a gift to 3, and employee 3 gives a gift to 1.
- Total gift value for this chain = 20 + 30 + 40 = 90.
- Chain 2 involves employees 4 and 5:
- Employee 4 gives a gift to 5, and employee 5 gives a gift to 4.
- Total gift value for this chain = 25 + 35 = 60.
The result table is ordered by the chain length and total gift value of the chain in descending order.
解法
方法一
1 | |