Разбиение на пары

Для начала рассмотрим тех агентов, которые хотят работать со своими коллегами из того же агенства. Объединим их между собой столько сколько возможно. При этом если агентов с такими предпочтениями нечетное количество, то их мы пока что отложим в недовольных. Очевидно, что иметь пары, где оба агента довольны выгодно, так как в случае другого разбиения кто-то из них может быть не доволен и ответ не улучшиться.

Затем рассмотрим тех, кто хочет работать с другим агентством. Пусть Кингсманов из них больше чем Стейтсманов (обратный вариант рассматривается аналогично) и сформируем из них наибольшее возможное количество пар. После объединения в остатке получим какое-то количество агентов Кингсман. Кому-то из них можно дать в пару остаток от агентов из раньше рассмотренных предпочтений, таким образом сформируем до двух пар, где ровно один доволен.

Остальные, к сожалению, будут иметь дискомфорт. Останется только вывести их число.