Задача про винты и гнезда

Разгребая старые записи, я нашел несколько задач, виденных мной на различных интервью.

Вот одна из них.

Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить: (1) винт тоньще гнезда - не подходит, (2) винт толще гнезда - не подходит, (3) или винт точно входит в гнездо - подходит.

Сравнивать винты или гнезда между собой нельзя.

Очевидное решение за O(N^2) - попробовать каждый болт последовательно в каждое гнездо до совпадения. Но есть решение быстрее.