Раздать телефоны покупателям по наилучшим ценам

Красивая задача с собеседования: очевидное решение через MIN(price) неверно, и интервьюер ждёт, что ты сам заметишь подвох.

Задача

Со склада нужно раздать телефоны покупателям по наилучшим ценам. Две таблицы:

• wanted(name) — модели, которые хотят купить. Возможны повторы: несколько человек хотят одну модель.
• stock(name, price) — телефоны на складе с ценами. У одной модели может быть несколько единиц по разным ценам.

Каждому желающему выдай цену. Правило: каждая единица товара продаётся один раз. Если nokia хотят двое, один получит дешевле, другой — следующую по цене. Если модели на складе нет — цена NULL.

Схема данных

CREATE TABLE wanted (name text);
CREATE TABLE stock (name text, price numeric);

В песочнице nokia хотят трое, а на складе три nokia по разным ценам — их и надо распределить по очереди.

Решение

WITH demand AS (
  SELECT name, ROW_NUMBER() OVER (PARTITION BY name ORDER BY name) AS rn
  FROM wanted
),
supply AS (
  SELECT name, price, ROW_NUMBER() OVER (PARTITION BY name ORDER BY price) AS rn
  FROM stock
)
SELECT d.name, s.price
FROM demand d
LEFT JOIN supply s ON s.name = d.name AND s.rn = d.rn
ORDER BY d.name, d.rn;

Разбор

Ловушка — GROUP BY name с MIN(price). Так самый дешёвый телефон модели «продастся» сразу всем желающим этой модели, хотя единица одна. Спрос и предложение нельзя схлопывать — их надо выстроить в очередь и сопоставить по позиции.

Приём: нумеруем обе стороны. В supply номер раздаём по возрастанию цены (ORDER BY price) — первая единица самая дешёвая, вторая дороже и так далее. В demand просто нумеруем желающих внутри модели. Теперь LEFT JOIN по паре (name, rn) сажает первого желающего на первую (самую дешёвую) единицу, второго — на вторую, и так далее.

Почему именно LEFT JOIN, а не INNER: он сохраняет желающих, которым единицы не хватило (номер спроса больше, чем есть единиц) или у которых модели вовсе нет на складе. У таких price окажется NULL — ровно как требует условие. На данных песочницы третий желающий nokia получает самую дорогую единицу, а желающий samsung — NULL, потому что samsung на складе нет. Про то, как LEFT JOIN сохраняет строки без пары, — в вопросе виды JOIN и их различия.

Ожидаемый результат

name | price
--- | ---
iphone | 500
nokia | 100
nokia | 150
nokia | 200
samsung | NULL