Problem

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 1000kilograms , 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.

The result format is in the following example.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

Input: 
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    |
+-----------+-------------+--------+------+
Output: 
+-------------+
| person_name |
+-------------+
| John Cena   |
+-------------+
Explanation: The folowing 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    | ___          |
+------+----+-----------+--------+--------------+

## Solution

### Method 1 – Cumulative Sum with Window

#### Intuition

We need to simulate the boarding process in order of `turn`, keeping a running total of the weights. The last person who boards without exceeding the weight limit is our answer. This is a classic cumulative sum problem with an early stop.

#### Approach

1. Sort the people by `turn` ascending.
2. Iterate through the sorted list, maintaining a running sum of weights.
3. For each person, if adding their weight does not exceed the weight limit, update the answer to their name.
4. Stop when the next person would exceed the limit.

#### Code



    

         
         
         
        
            
            
        
            
            
                 
                 
                
            
        
            
            
        
            
            
                 
                 
                
            
        
            
            
        
            
            
                 
                 
                
            
        
            
            
        
    


    

        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18




SELECT person_name
FROM (
  SELECT person_name, SUM(weight) OVER (ORDER BY turn) AS total_weight, weight, turn
  FROM Queue
) t
WHERE total_weight <= (
  SELECT SUM(weight) FROM (
    SELECT weight FROM Queue ORDER BY turn
  ) t2
  WHERE (
    SELECT SUM(weight) FROM (
      SELECT weight FROM Queue ORDER BY turn
      LIMIT 1000000
    ) t3
  ) >= total_weight
)
ORDER BY total_weight DESC
LIMIT 1;





        

        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14




WITH ordered AS (
  SELECT person_name, weight, turn, SUM(weight) OVER (ORDER BY turn) AS total_weight
  FROM Queue
),
fit AS (
  SELECT person_name, total_weight
  FROM ordered
  WHERE total_weight <= (
    SELECT MAX(total_weight) FROM ordered WHERE total_weight <= (
      SELECT MAX(total_weight) FROM ordered
    )
  )
)
SELECT person_name FROM fit ORDER BY total_weight DESC LIMIT 1;





        

        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            




 1
 2
 3
 4
 5
 6
 7
 8
 9
10




def last_person_to_fit(df, weight_limit):
    df = df.sort_values('turn')
    total = 0
    ans = ''
    for _, row in df.iterrows():
        if total + row['weight'] > weight_limit:
            break
        total += row['weight']
        ans = row['person_name']
    return ans





        

        
        
         
        
        
    





#### Complexity

- ⏰ Time complexity: `O(n log n)` for sorting by turn, then `O(n)` for the scan. Overall: `O(n log n)`.
- 🧺 Space complexity: `O(n)` for sorting and cumulative sum arrays.