題目敘述
題目會給我們一張資料表Queue，代表乘客排隊上車的情境。
裡面分別有person_id、 person_name 、weight、turn等欄位，分別代表乘客ID、乘客姓名、乘客重量、乘客排隊的順序。其中person_id做為主鍵Primary key要求我們判斷，在不超重(乘客總重量在1000 公斤以內)的條件下，最後一位上車的乘客是誰?
題目額外保證，一定存在一組解答。
測試範例
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 | ___ |
+------+----+-----------+--------+--------------+
演算法
主要有兩個考察點。
- 聯想到用Prefix sum前綴和: 用乘客體重的前綴和，方便之後去判斷最後一位可以安全上車的乘客是誰。
- 使用分群 和 排序語法，輸出最後一位可以安全上車的乘客ID。
- 計算乘客體重的前綴和
# 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
- 結合 分群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;
關鍵知識點
- 聯想到用Prefix sum前綴和: 用乘客體重的前綴和，方便之後去判斷最後一位可以安全上車的乘客是誰。這點比較困難，可以在學會之後，多在紙筆或SQL平台上練習幾次，增加熟練度。
- 使用分群 和 排序語法，輸出最後一位可以安全上車的乘客ID。
Reference:
[1] MySQL by prefix sum of weight [w/ Comment] - Last Person to Fit in the Bus - LeetCode
