Last Person to Fit in the Bus

Table: Queue

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| person_id   | int     |
| person_name | varchar |
| weight      | int     |
| turn        | int     |
+-------------+---------+

person_id column contains unique values. This table has the information about all people waiting for a bus. The person_id and turn columns will contain all numbers from 1 to n, where n is the number of rows in the table. turn determines the order of which the people will board the bus, where turn=1 denotes the first person to board and turn=n denotes the last person to board. weight is the weight of the person in kilograms.

There is a queue of people waiting to board a bus. However, the bus has a weight limit of 1000 kilograms, so there may be some people who cannot board.

Write a SQL query to find the person_name of the last person that can fit on the bus without exceeding the weight limit. The test cases are generated such that the first person does not exceed the weight limit.

Note that only one person can board the bus at any given turn.

For example, given the following 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    |
+-----------+-------------+--------+------+

The query should return:

+-------------+
| person_name |
+-------------+
| John Cena   |
+-------------+

Explanation: The following 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    | ___          |
+------+----+-----------+--------+--------------+

SELECT person_name
FROM (
    SELECT person_name, SUM(weight) OVER (ORDER BY turn) AS cumulative_weight
    FROM Queue
) AS subquery
WHERE cumulative_weight <= 1000
ORDER BY cumulative_weight DESC
LIMIT 1;

Explanation:

1. Subquery for Cumulative Weight:

• The inner SELECT statement calculates the cumulative weight of people boarding the bus based on their turn order.
• SUM(weight) OVER (ORDER BY turn) is a window function that calculates a running sum of the weight column, ordered by the turn column. This gives us the total weight on the bus after each person boards.

1. Filtering by Weight Limit:

• The outer SELECT statement filters the results from the subquery to only include people for whom the cumulative_weight is less than or equal to 1000 (the bus's weight limit).

1. Finding the Last Person:

• ORDER BY cumulative_weight DESC sorts the filtered results in descending order of cumulative weight. This puts the person who caused the total weight to reach closest to 1000 (without exceeding it) at the top.
• LIMIT 1 selects only the first row, which corresponds to the last person who could board the bus without exceeding the weight limit.

Alternative Solution using a variable:

SET @running_weight := 0;

SELECT person_name
FROM (
    SELECT
        person_name,
        @running_weight := @running_weight + weight AS cumulative_weight
    FROM Queue
    ORDER BY turn
) AS subquery
WHERE cumulative_weight <= 1000
ORDER BY cumulative_weight DESC
LIMIT 1;

Explanation:

1. Initialize a variable:

• SET @running_weight := 0; initializes a user-defined variable @running_weight to 0. This variable will store the cumulative weight as we iterate through the queue.

1. Subquery for Cumulative Weight:

• The inner SELECT statement calculates the cumulative weight of each person boarding the bus.
• @running_weight := @running_weight + weight updates the @running_weight variable by adding the current person's weight to it. The := operator is used for assignment within the query.
• AS cumulative_weight assigns the updated value of @running_weight to the alias cumulative_weight for each row.
• ORDER BY turn ensures that the queue is processed in the correct order.

1. Filtering by Weight Limit and selecting the last person:

• The outer SELECT statement filters the results from the subquery to only include people for whom the cumulative_weight is less than or equal to 1000 (the bus's weight limit).
• ORDER BY cumulative_weight DESC sorts the filtered results in descending order of cumulative weight.
• LIMIT 1 selects only the first row, which corresponds to the last person who could board the bus without exceeding the weight limit.