SQL 分群語法 公車上車的最後一位乘客 Leetcode #1204

Teddy O on Unsplash

題目敘述

題目會給我們一張資料表Queue，代表乘客排隊上車的情境。

裡面分別有person_id、 person_name 、weight、turn等欄位，分別代表乘客ID、乘客姓名、乘客重量、乘客排隊的順序。其中person_id做為主鍵Primary key

題目額外保證，一定存在一組解答。

詳細的題目可在這裡看到

測試範例

Example 1:

Input: 
Queue table:
+-----------+-------------+--------+------+
| person_id | person_name | weight | turn |
+-----------+-------------+--------+------+
| 5         | Alice       | 250    | 1    |
| 4         | Bob         | 175    | 5    |
| 3         | Alex        | 350    | 2    |
| 6         | John Cena   | 400    | 3    |
| 1         | Winston     | 500    | 6    |
| 2         | Marie       | 200    | 4    |
+-----------+-------------+--------+------+

Output: 
+-------------+
| person_name |
+-------------+
| John Cena   |
+-------------+

Explanation: The folowing table is ordered by the turn for simplicity.
+------+----+-----------+--------+--------------+
| Turn | ID | Name      | Weight | Total Weight |
+------+----+-----------+--------+--------------+
| 1    | 5  | Alice     | 250    | 250          |
| 2    | 3  | Alex      | 350    | 600          |
| 3    | 6  | John Cena | 400    | 1000         | (last person to board)
| 4    | 2  | Marie     | 200    | 1200         | (cannot board)
| 5    | 4  | Bob       | 175    | ___          |
| 6    | 1  | Winston   | 500    | ___          |
+------+----+-----------+--------+--------------+

演算法

主要有兩個考察點。

1. 聯想到用Prefix sum前綴和: 用乘客體重的前綴和，方便之後去判斷最後一位可以安全上車的乘客是誰。
2. 使用分群 和 排序語法，輸出最後一位可以安全上車的乘客ID。

1. 計算乘客體重的前綴和

# Write your MySQL query statement below
SELECT q1.person_name
FROM Queue AS q1
INNER JOIN Queue AS q2
# Prefix sum of weight to each passenger
ON q1.turn >= q2.turn

2. 結合 分群GROUP BY 和 排序 ORDER BY語法，輸出最後一位可以安全上車的乘客ID。

GROUP BY q1.turn

# Weight limit 1000 Kg
HAVING SUM(q2.weight) <= 1000

# Sort total weight on descending order
ORDER BY SUM(q2.weight) DESC
# Last one
LIMIT 1;

程式碼

換行的空白只是方便讀者閱讀理解，實際上可以拿掉。

SELECT q1.person_name
FROM Queue AS q1
INNER JOIN Queue AS q2
# Prefix sum of weight to each passenger
ON q1.turn >= q2.turn
GROUP BY q1.turn

# Weight limit 1000 Kg
HAVING SUM(q2.weight) <= 1000

# Sort total weight on descending order
ORDER BY SUM(q2.weight) DESC
# Last one
LIMIT 1;

關鍵知識點

1. 聯想到用Prefix sum前綴和: 用乘客體重的前綴和，方便之後去判斷最後一位可以安全上車的乘客是誰。這點比較困難，可以在學會之後，多在紙筆或SQL平台上練習幾次，增加熟練度。

1. 使用分群 和 排序語法，輸出最後一位可以安全上車的乘客ID。

Reference:

[1] MySQL by prefix sum of weight [w/ Comment] - Last Person to Fit in the Bus - LeetCode