Оптимальная стратегия для предложения работы

Question

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

Как решить такие типы вопросов? Заранее спасибо.

Answer 1

Предположим, что работодатель собирается нанять N employee из одного круга друзей (все дружат со всеми в этом круге).

Таким образом, для каждого номера, i, от 1 до n, должно быть не менее i людей, которые принимают работу, когда i-1 их друзей приняли предложение. В противном случае возникнет тупик.

Например, допустим, N равно 5.

There should be at least 1 person accepting the job without any friend accepting it (k=0).
Similarly, 2 people with at most 1 friend accepting the job(k=1). 
3 people with at most 2 of their friends accepting the job (k=2).

и т. Д.

В противном случае никто не примет работу, котораяэто тупик, как упомянуто в комментариях.

Если зафиксировано k, есть только одно решение, когда k==0, как упоминалось @norok2.