Skip to main content
4 of 6
added links.
Nicholas Mancuso
  • 3.9k
  • 1
  • 24
  • 39

Let $P$ be the set of people and $\mathcal{S}$ be the modified multi-set of subsets. By checking if a $P$-saturated matching into $\mathcal{S}$ exists (i.e. Hall's condition) you are indeed checking that your groups are diverse. If you are "checking" if some group is a solution, simply make $P$ this group and solve. If some member in $P$ is not matched, then you cannot construct a "diverse group".

This can be done quickly via the Hopcraft-Karp algorithm (as you don't have weights over edges) or by implementing this as a Max-flow LP and using a solver. I'm willing to bet the solvers will work much faster in practice.

Nicholas Mancuso
  • 3.9k
  • 1
  • 24
  • 39