Problem: Last Person to Fit in the Bus

The problem requires finding the name of the last person who can board a bus with a weight limit of 1000 kg. The input is a Queue table containing information about people waiting to board, including their ID, name, weight, and boarding order (turn).

Solutions Explained

Two SQL solutions are provided, both leveraging the power of SQL window functions and aggregation. Let's analyze each:

Solution 1: Cumulative Sum with Self-Join

This approach uses a self-join to calculate the cumulative weight up to each person's turn.

Code (MySQL):

SELECT a.person_name
FROM
    Queue AS a,
    Queue AS b
WHERE a.turn >= b.turn
GROUP BY a.person_id
HAVING SUM(b.weight) <= 1000
ORDER BY a.turn DESC
LIMIT 1;

Explanation:

1. Self-Join: The query performs a self-join of the Queue table (aliased as a and b). The WHERE a.turn >= b.turn clause ensures that for each person (a), we sum the weights of all people with turns less than or equal to that person's turn.

2. Grouping and Aggregation: GROUP BY a.person_id groups the results by each person. SUM(b.weight) calculates the cumulative weight for each person's group.

3. Filtering: HAVING SUM(b.weight) <= 1000 filters out groups whose cumulative weight exceeds the limit.

4. Ordering and Limiting: ORDER BY a.turn DESC orders the results by turn in descending order (latest turn first). LIMIT 1 selects only the top result—the last person who fits.

Time Complexity: The self-join dominates the complexity, making it O(N^2) in the worst case, where N is the number of people in the queue. This is because for each person, the query sums the weights of all preceding people.

Space Complexity: The space complexity depends on the size of the intermediate result set generated by the join and aggregation. In the worst case, it could be O(N).

Solution 2: Window Function for Cumulative Sum

This solution uses a window function to efficiently calculate the cumulative weight. It is significantly more efficient than the self-join approach.

Code (MySQL):

WITH
    T AS (
        SELECT
            person_name,
            SUM(weight) OVER (ORDER BY turn) AS s
        FROM Queue
    )
SELECT person_name
FROM T
WHERE s <= 1000
ORDER BY s DESC
LIMIT 1;

Explanation:

1. Common Table Expression (CTE): A CTE named T is created to calculate the cumulative sum using the SUM() OVER (ORDER BY turn) window function. This efficiently computes the running total of weights ordered by the turn column.

2. Filtering and Ordering: The main query selects person_name from T, filters for rows where the cumulative sum (s) is less than or equal to 1000, orders the result in descending order of cumulative sum, and limits the result to the first row.

Time Complexity: This solution is significantly faster, with a time complexity of O(N), where N is the number of people in the queue. This is because the window function calculates the cumulative sum in a single pass.

Space Complexity: The space complexity is O(N) for storing the intermediate results in the CTE, but this is generally more efficient than the self-join's space usage in practice.

Conclusion

Solution 2 using the window function is the preferred and significantly more efficient approach due to its linear time complexity compared to the quadratic complexity of Solution 1. It leverages the optimized capabilities of SQL databases to handle cumulative calculations effectively.