1204 Last Person to Fit in the Bus

Description

Table: Queue

• 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.

Problem Statement

Write a solution 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.

The result format is in the following example.

Example 1:

Input:

• Queue table:

Output:

Explanation:

The folowing table is ordered by the turn for simplicity.

Solution

The problem essentially requires you to find the running sum of weight then you find the person with last turn which you can do if you order the results in descending order of total_weight WHERE total_weight <= 1000.

Let’s see how you can find the total_weight. You can find running total weight by using window function where you don’t partition by any field but rather order the rows by turn.

1SELECT person_id, person_name, weight, turn,
2    SUM(weight) OVER (ORDER BY turn)  AS total_weight
3    FROM Queue;

This returns below results.

The next step is to filter the records where total_weight is less than or equal to 1000. You can use WHERE total_weight <= 1000 clause. When you do this, you will get only the first three rows from above table. To find the last person to fit in the bus, you can order the result by total_weight DESC LIMIT 1 clause and print only person_name column.

Below is the final solution. Notice that I have calculated total_weight in CTE clause and removed unnecessary columns.

1WITH running_weight AS (
2    SELECT person_name, 
3        SUM(weight) OVER (ORDER BY turn)  AS total_weight
4        FROM Queue
5) SELECT person_name 
6    FROM running_weight
7    WHERE total_weight <= 1000
8    ORDER BY total_weight DESC
9    LIMIT 1;