last-person-to-fit-in-the-elevator.sql

/*

LeetCode Problem 1204.

Table: Queue

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| person_id   | int     |
| person_name | varchar |
| weight      | int     |
| turn        | int     |
+-------------+---------+
person_id is the primary key column for this table.
This table has the information about all people waiting for an elevator.
The person_id and turn columns will contain all numbers from 1 to n, where n is the number of rows in the table.
The maximum weight the elevator can hold is 1000.

Write an SQL query to find the person_name of the last person who will fit in the elevator without exceeding the weight limit. It is guaranteed that the person who is first in the queue can fit in the elevator.

The query result format is in the following example:

Queue table
+-----------+-------------------+--------+------+
| person_id | person_name       | weight | turn |
+-----------+-------------------+--------+------+
| 5         | George Washington | 250    | 1    |
| 3         | John Adams        | 350    | 2    |
| 6         | Thomas Jefferson  | 400    | 3    |
| 2         | Will Johnliams    | 200    | 4    |
| 4         | Thomas Jefferson  | 175    | 5    |
| 1         | James Elephant    | 500    | 6    |
+-----------+-------------------+--------+------+

Result table
+-------------------+
| person_name       |
+-------------------+
| Thomas Jefferson  |
+-------------------+

Queue table is ordered by turn in the example for simplicity.
In the example George Washington(id 5), John Adams(id 3) and Thomas Jefferson(id 6) will enter the elevator as their weight sum is 250 + 350 + 400 = 1000.
Thomas Jefferson(id 6) is the last person to fit in the elevator because he has the last turn in these three people.

*/

# V0
# IDEA : SUM + WINDOW FUNC
# https://stackoverflow.com/questions/10039431/how-can-i-use-sum-over
SELECT
person_name
FROM ( 
SELECT
person_name
FROM
Queue
WHERE SUM(weight) OVER (PARTITION BY person_name ORDER BY turn) >= 1000
) sub

# V0' : sub query and select same table twice
### NOTE : the where condition : where a.turn >= turn
select person_name 
from queue a
where (select sum(weight) 
       from queue 
       where a.turn >= turn) <= 1000
order by turn desc 
limit 1

# V1
# https://circlecoder.com/last-person-to-fit-in-the-elevator/
select person_name 
from queue a
where (select sum(weight) 
       from queue 
       where a.turn >= turn) <= 1000
order by turn desc 
limit 1

# V2
# Time:  O(nlogn) 
# Space: O(n) 
SELECT person_name 
FROM   (SELECT person_name, 
               @accu := @accu + weight AS accu 
        FROM   (SELECT person_name, weight
                FROM   Queue 
                ORDER  BY turn) q, 
               (SELECT @accu := 0) vars) t 
WHERE  accu <= 1000 
ORDER  BY accu DESC 
LIMIT  1;