SQL Q. series 1 - Last Person to Fit in the Bus 🚌🚌

#sql #programming

Can you solve this LeetCode SQL question ?

Table: Queue

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

person_id column contains unique values.
Q). This Queue 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 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.

Ans -

First approach calculate max weight

SELECT SUM(weight) from queue;

But it will give only sum of all weights. We want to sum the weights of persons but iteratively and by their turn.

OVER CLAUSE

We can use OVER clause with aggregate function in this case SUM to SUM OVER turn column which is ORDER BY turn meaning it will sum weight repeatedly over column turn where turns starting from 1 to n.

SELECT
    PERSON_NAME,
    WEIGHT,
    TURN,
    SUM(WEIGHT) OVER (
        ORDER BY
            TURN
    ) AS ACCUMULATED_WEIGHT
FROM
    QUEUE

It will give following result -

person_name	weight	turn	accumulated_weight
Alice	250	1	250
Alex	350	2	600
John Cena	400	3	1000
Marie	200	4	1200
Bob	175	5	1375
Winston	500	6	1875

Notice all accumulated_weight is sum of all previous weights and also it is order by turn.

Now we just need to get all rows where accumulated_weight >=1000
We can do that by using SQL sub-query and where condition as below -

SELECT
    PERSON_NAME,
    WEIGHT,
    TURN,
    ACCUMULATED_WEIGHT
FROM
    (
        SELECT
            PERSON_NAME,
            WEIGHT,
            TURN,
            SUM(WEIGHT) OVER (
                ORDER BY
                    TURN
            ) AS ACCUMULATED_WEIGHT
        FROM
            QUEUE
    )
WHERE ACCUMULATED_WEIGHT<=1000

Which give us

PERSON_NAME	WEIGHT	TURN	ACCUMULATED_WEIGHT
Alice	250	1	250
Alex	350	2	600
John Cena	400	3	1000

we see when John Cena board the bus weight limit exceeds. so we just need to sort this result in DESC order and get the top result by LIMIT 1;

SELECT
    PERSON_NAME,
    WEIGHT,
    TURN,
    ACCUMULATED_WEIGHT
FROM
    (
        SELECT
            PERSON_NAME,
            WEIGHT,
            TURN,
            SUM(WEIGHT) OVER (
                ORDER BY
                    TURN
            ) AS ACCUMULATED_WEIGHT
        FROM
            QUEUE
    )
WHERE ACCUMULATED_WEIGHT<=1000
ORDER BY ACCUMULATED_WEIGHT DESC LIMIT 1

which will give us ans -

PERSON_NAME	WEIGHT	TURN	ACCUMULATED_WEIGHT
John Cena	400	3	1000

DEV Community

SQL Q. series 1 - Last Person to Fit in the Bus 🚌🚌

OVER CLAUSE

Top comments (0)