Условие

Таблица Queue(person_id, person_name, weight, turn) — очередь людей на автобус. Лимит автобуса 1000 кг. Люди заходят по возрастанию turn. Найдите имя последнего, кто поместился (накопительный вес ≤ 1000).

Решение

Идея — running total и MAX(turn) среди допустимых

WITH cumulative AS (
  SELECT
    person_id, person_name, turn, weight,
    SUM(weight) OVER (ORDER BY turn ROWS UNBOUNDED PRECEDING) AS cum_weight
  FROM Queue
)
SELECT person_name
FROM cumulative
WHERE cum_weight <= 1000
ORDER BY turn DESC
LIMIT 1;

Объяснение

SUM OVER (ORDER BY turn) даёт накопительный вес ровно после того, как этот человек зашёл. Фильтр cum_weight <= 1000 оставляет всех, кто поместился; ORDER BY turn DESC LIMIT 1 берёт последнего.

Без оконной функции — коррелированный подзапрос

SELECT person_name
FROM Queue q1
WHERE (SELECT SUM(weight) FROM Queue q2 WHERE q2.turn <= q1.turn) <= 1000
ORDER BY q1.turn DESC
LIMIT 1;

O(N²) — для интервью с упоминанием перфоманса показывает понимание сложности.

Подводные камни

ROWS UNBOUNDED PRECEDING vs default. Default фрейм для ORDER BY без ROWS — это RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW. Если есть равные turn (не должно быть, но...), RANGE захватит всех с тем же turn — даст другой результат.
Что если первый же человек > 1000 кг. Запрос вернёт пусто — нужно ли вернуть NULL? В задаче гарантируется хотя бы один помещается.
Сортировка. ORDER BY turn DESC — иначе LIMIT 1 возьмёт первого помещающегося, а не последнего.

Эталонный ответ

SUM(weight) OVER (ORDER BY turn) + WHERE cum <= 1000 + ORDER BY turn DESC LIMIT 1. Не MAX(cum), потому что нужен последний по очереди, а не самый «тяжёлый» допустимый.

LeetCode SQL — Last Person to Fit in the Bus: накопительная сумма по очереди