Last Person to Fit in the Bus
Problem
People board a bus one at a time in order of their turn. Each person has a weight, and the bus can carry at most 1000 kilograms. People keep boarding as long as the bus does not exceed the limit; the first person who would push the total over 1000 (and everyone after) stays behind. Return the name of the last person who fits on the bus.
turns = [(Alice,250), (Alex,350), (John,400), (Cynthia,250)]JohnSELECT q1.person_name
FROM Queue q1 JOIN Queue q2 ON q1.turn >= q2.turn
GROUP BY q1.turn, q1.person_name, q1.weight
HAVING SUM(q2.weight) <= 1000
ORDER BY SUM(q2.weight) DESC
LIMIT 1;Explanation
The key insight is that the people board in order of their turn, so the bus weight at the moment a person sits down is just the sum of every person's weight up to and including them. That sum is a classic running total (a prefix sum), and we want the last person whose running total still fits under 1000.
This SQL does exactly that with a clever self-join. For each person q1, it joins every earlier-or-equal person q2 (the condition q1.turn >= q2.turn), then GROUP BY collapses them so SUM(q2.weight) becomes the running total at q1's seat.
The HAVING SUM(q2.weight) <= 1000 filter throws away anyone whose running total would exceed the limit. Among the survivors we want the one with the largest running total, since that is the last person to board, so we ORDER BY SUM(q2.weight) DESC and take LIMIT 1.
Example: running totals are Alice 250, Alex 600, John 1000, Cynthia 1250. Cynthia's 1250 fails the HAVING check and drops out. Of the rest, John's 1000 is the biggest that still fits, so John is returned.