CODEWITHSUNDEEP
algorithmgraph-algorithm
viablehacker
viablehacker

Reputation: 21

Matching people with people they don't already know

So I'm stuck on a problem. Here's the problem: I have a bunch of people males and females these people have friends (could be hundreds) and hours they are free to meet people (e.g. 19:00, 20:00, 21:00). I want to match them as efficiently as possible so that as few people as possible remain unmatched. The rules are that you have to be matched with someone of the opposite sex, a match cannot be a friend and your match has to have the same hour available as you.

I would really appreciate some pointers on this one. Thanks in advance!

Upvotes: 2

Views: 106

Answers (1)

borrible
borrible

Reputation: 17356

You are looking at maximum cardinality bipartite matching. Your graph is a bipartite one (i.e. splittable in to two sets of nodes) where one set are male and the other set female. An edge exists between two nodes if your conditions are met.

Upvotes: 4

Related Questions