language agnostic - What is a better algorithm than brute force to separate items in overlapping categories? -

i have arbitrary set of items (dots below), , number of categories overlapping in arbitrary way (a-c below). test determine whether it's possible each item assigned single category, among ones belongs to, such each category ends @ least number of items.

so example, may require a, b, , c can each claim one item. if we're given 4 dots below, showing possible easy: stick items in list, loop through categories, , have each category remove item has access too, , long each category able remove 1 item, pass test.

now suppose remove blue dot , repeat test. can assign yellow a, red b, , green c, , again pass. it's hard codify solution: if follow previous method (again no blue dot), suppose starts removing green dot. if b removes yellow dot, we'll fail test (since c can't remove red dot), whereas if b removes red dot, c can still take yellow , pass.

one solve brute force iterating through every possible assignment of items categories, checking see if condition met each iteration, won't scale arbitrary numbers of items , categories, , have feeling there's smarter or more efficient way.

i don't know name of problem, makes hard research. have optimal solution? if so, kind of complexity can expect solution?

you right point out it's assignment problem, , such, can solved using graph theory classic algorithms.

you can translate problem follows:

the nodes on 1 side represent categories , nodes on other side represent items. want find maximal match. problem can reduced finding maximal flow in bi-partite graph.

fold-fulkerson can used find maximum matching in bipartite graph in o(es) e number of edges , s maximal flow in network.