medium Last Person to Fit in the Elevator

Problem Statement

Table: ElevatorQueue

This table stores information about individuals waiting for an elevator. Each row includes a person's ID, their name, their weight, and their position in the queue.

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| person_id     | int     |
| name          | varchar |
| weight        | int     |
| position      | int     |
+---------------+---------+
person_id column contains unique values.
This table contains data about all individuals queuing for an elevator.
The person_id and position columns will contain all numbers from 1 to n, where n is the number of rows in the table.
position determines the queue order for boarding the elevator, where position=1 denotes the first person in the queue and position=n denotes the last person in the queue.
weight is the weight of the individual in kilograms.

The elevator has a maximum weight capacity of 800 kilograms. It's possible that not everyone in the queue will be able to board the elevator without exceeding this limit.

Develop a solution to identify the name of the last individual who can board the elevator without surpassing the weight capacity. Assume that the first individual in the queue does not exceed the weight limit.

Return the result in the format provided in the example.

Example

Input:

ElevatorQueue table:
+-----------+------------+--------+----------+
| person_id | name       | weight | position |
+-----------+------------+--------+----------+
| 1         | Alice      | 200    | 1        |
| 2         | Bob        | 150    | 4        |
| 3         | Charlie    | 300    | 2        |
| 4         | Dave       | 225    | 5        |
| 5         | Eve        | 175    | 3        |
| 6         | Fiona      | 350    | 6        |
+-----------+------------+--------+----------+

Output:

+------+
| name |
+------+
| Eve  |
+------+

Try It Yourself

-- TODO: Write your user queries here

Solution

To determine the last individual who can board the elevator without exceeding the 800-kilogram weight limit, we'll follow a streamlined approach that aligns directly with the SQL query provided.

1. Order Individuals by Position: Start by arranging the individuals based on their position in the queue to respect the boarding order.
2. Calculate Cumulative Weight: Compute a running total of weights as we move down the queue. This helps in identifying when the cumulative weight approaches or exceeds the elevator's capacity.
3. Identify the Last Eligible Individual: From the cumulative weights, select the last person whose addition doesn't breach the 800-kilogram limit.

SQL Query

WITH CumulativeWeight AS (
    SELECT name, weight, SUM(weight) OVER (ORDER BY position) AS total_weight
    FROM ElevatorQueue
)
SELECT name
FROM CumulativeWeight
WHERE total_weight <= 800
ORDER BY total_weight DESC
LIMIT 1;

Step-by-Step Approach

Step 1: Order by Position and Calculate Cumulative Weight

We utilize a Common Table Expression (CTE) named CumulativeWeight to:

• Order the individuals based on their position.
• Calculate the cumulative weight up to each person in the queue using the SUM() OVER (ORDER BY position) window function.

WITH CumulativeWeight AS (
    SELECT 
        name, 
        weight, 
        SUM(weight) OVER (ORDER BY position) AS total_weight
    FROM 
        ElevatorQueue
)

Explanation:

• The SUM(weight) OVER (ORDER BY position) computes the running total of weights as per the queue order.
• This CTE prepares the data for the next step by providing the cumulative weights alongside each individual's name.

Step 2: Select the Last Individual Within Capacity

From the CumulativeWeight CTE, we:

• Filter individuals where the total_weight is less than or equal to 800 kilograms.
• Order the filtered results in descending order of total_weight to prioritize the heaviest possible cumulative weight without exceeding the limit.
• Limit the result to the top entry, which represents the last person who can board without surpassing the capacity.

SELECT 
    name
FROM 
    CumulativeWeight
WHERE 
    total_weight <= 800
ORDER BY 
    total_weight DESC
LIMIT 1;

Explanation:

• WHERE total_weight <= 800 ensures we only consider scenarios where the elevator's capacity isn't exceeded.
• ORDER BY total_weight DESC arranges the eligible individuals so that the one with the highest cumulative weight is at the top.
• LIMIT 1 retrieves the single name that fits the criteria, representing the last person who can board safely.

Final Output:

+------+
| name |
+------+
| Eve  |
+------+

I'm working on the problem **Last Person to Fit in the Elevator** (Databases). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Last Person to Fit in the Elevator** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Last Person to Fit in the Elevator**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Last Person to Fit in the Elevator**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.