Предположим, у вас есть набор людей J, и вам нужно сфотографировать каждого человека. У них есть только один фотограф, и у фотографа есть конечное количество раз T (|T| > |J|), доступных для каждой фотографии. В любой момент времени t из T фотограф может сделать только одну фотографию. Каждый человек в J доступен для фотографирования только в определенное время в T, хотя каждого человека попросили выбрать хотя бы один раз, когда он доступен. По сути, в зависимости от доступности каждого человека фотограф хочет попытаться назначить одного человека на каждый доступный временной интервал в T, чтобы каждый мог сфотографироваться. Существует ли алгоритм с полиномиальным временем для решения этой задачи? Если нет, то какая задача неполиномиального времени сводится к этой задаче за полиномиальное время, т. е. как показать, что этой задачи нет в P?
Пример:
Фотограф доступен в [1, 12, 15, 33, 45, 77].
Человек А доступен в [12, 33].
Человек Б доступен в [1, 12].
Человек С доступен в [1, 12].
Мы можем сфотографировать всех, выбрав:
Человек А: 33
Человек Б: 1
Человек В: 12
Если бы мы начали с выбора A: 12, B: 1, мы не смогли бы найти место для C, т. е. нам пришлось бы вернуться назад и переназначить A на 33.
По сути, я ищу алгоритм полиномиального времени, чтобы найти подходящее назначение времени, если оно существует, и в противном случае иметь возможность сообщить, что подходящее назначение не существует.
