Это вопрос из интервью, с которым я недавно столкнулся. У вас есть G гостей (пронумерованных от 1 до G) на вечеринке. У каждого гостя есть список предпочтений длиной G, который представляет его предпочтения в общении с другими. Например, если список предпочтений гостя 1 N Y N N Y (при условии, что гостей 5), то гость 1 заинтересован в разговоре либо с 2, либо с 5, но не с другими.
Предположить, что
а) Каждый гость может поговорить только с одним другим гостем
б) Если a заинтересован в разговоре с b , то b также заинтересован в разговоре с a
Учитывая матрицу гостей и их предпочтения, дайте максимальное количество пар, которые могут оставаться занятыми.
Let G = 5;
Матрица предпочтений
N Y N N N
Y N Y Y Y
N Y N N N
N Y N N N
N Y N N N
Как мы видим, всем интересно поговорить с Гостем 2, но он может поговорить только с одним другим человеком, поэтому ответ — 1 пара.
Мой подход:
Я думал об этом как о проблеме максимального соответствия в теории графов, но не смог реализовать ее в короткие сроки (я не очень хорошо разбираюсь в реализации графического алгоритма)
Это решается только с помощью графиков или есть более быстрый и лучший подход?
Существует ли жадный подход?
