Алгоритм сопряжения двух неравных списков с парными ограничениями

Question

Мне нужно создать алгоритм, в котором у меня есть два списка неравного размера, которые называются "Студенты и учителя". Учеников намного больше, чем Учителей. Мне нужно создать пару для каждого Ученика, где каждый Учитель сопоставляется с примерно одинаковым количеством Учеников.

Сложность в том, что у меня есть набор пар, которые неприемлемы. В частности, у каждого ученика может быть один или несколько учителей, с которыми он не может быть в паре.

Я знаю, что мог бы создать очень эффективный жадный алгоритм, который просто начинает произвольно сопоставлять совпадения и пропускает совпадения, которые не работают, поскольку число учеников, которым назначен каждый учитель, не обязательно должно быть точным. Независимо от того, я хотел бы эффективный и полный способ сделать это. Спасибо за любой совет, который вы можете предложить!

Answer 1

Я бы начал с самого ограниченного соответствия до менее ограниченного, это оставит неограниченное соответствие последним, и вы можете использовать их для баланса.