Algorithm to categorize items
I'm trying to figure out if this test has a general name and / or solution.
I have some arbitrary set of items (dots below), and some number of
categories overlapping in an arbitrary way (A-C below). The test is to
determine whether it's possible for each item to be assigned to a single
category, among the ones it already belongs to, such that each category
ends up with at least some number of items.
So for example, we may require that A, B, and C can each claim one item.
If we're given all 4 dots below, showing that this is possible is easy:
just stick all the items in a list, loop through the categories, and have
each category remove an item that it has access too, and as long as each
category is able to remove one item, we pass the test.
Now suppose we remove the blue dot and repeat the test. Clearly we can
assign yellow to A, red to B, and green to C, and again we pass. But it's
hard to codify this solution: if we follow the previous method (again no
blue dot), then suppose A starts by removing the green dot. Now if B
removes the yellow dot, we'll fail the test (since C can't remove the red
dot), whereas if B removes the red dot, C can still take yellow and pass.
One could solve this by bruit force by iterating through every possible
assignment of items to categories, checking to see if the condition is met
with each iteration, but this won't scale well to arbitrary numbers of
items and categories, and I have a feeling there's a smarter / more
efficient way.
So: does this problem have a name? Does it have an optimal solution? What
kind of complexity can I expect for the solution?
Bonus question: given that I'm implementing this in C++, is there some
library I should look into to solve it?