Алгоритм планирования встреч (N человек с N свободными слотами, ограничение-удовлетворение)

Постановка задачи

У нас есть один работодатель, который хочет провести собеседование с N людьми, и поэтому выделяет N слотов для интервью. У каждого человека есть свободный график для этих слотов. Предложите алгоритм, который распределяет N людей по N слотам, если это возможно, и возвращает флаг/ошибку/и т. д., если это невозможно. Какова максимально возможная сложность времени выполнения?

Мои подходы до сих пор

Наивный: есть N! способы запланировать N человек. Пройдите их все, для каждой перестановки проверьте, выполнимо ли это. O( n! )

Возврат:

1. Ищите все интервалы времени интервью, в которых может быть только 1 человек. Запланируйте человека, удалите его из списка кандидатов и уберите слот.
2. Ищите кандидатов, которые могут попасть только в 1 слот. Запланируйте человека, удалите его из списка кандидатов и уберите слот.
3. Повторяйте 1 и 2, пока не останется таких комбинаций.
4. Выберите человека, запланируйте его случайным образом в один из доступных слотов. Запомните эту операцию.
5. Повторяйте 1, 2, 3, пока у нас не будет расписания или не возникнет неразрешимый конфликт. Если у нас есть расписание, верните его. Если есть неразрешимый конфликт, отступите.

Думаю, это O(n!) наихудшего случая, который ничем не лучше.

Там может быть Д.П. решение тоже - но я его еще не вижу.

Другие мысли

Проблема может быть представлена ​​в виде матрицы NxN, где строки — это «слоты», столбцы — «люди», а значения «1» — «свободно» и «0» — «занято». Затем мы ищем в этой матрице матрицу идентичности с перестановкой строк и столбцов. Шаги 1 и 2 ищут строку или столбец только с одной «1». (Если ранг матрицы = N, I это означает, что решение есть. Но обратное неверно) Другой способ взглянуть на это - рассматривать матрицу как невзвешенную матрицу ребер ориентированного графа. Затем каждый узел представляет 1 кандидата и 1 слот. Затем мы ищем набор ребер, чтобы каждый узел в графе имел одно исходящее ребро и одно входящее ребро. Или, с 2 узлами, это будет двудольный граф.

Пример матрицы:

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1