What's the name of this algorithm?

72 views Asked by At

I've been searching for the name of this problem I have to do an assignment on, determine if it's P or NP, etc. But I can't find it anywhere. Here's the problem:

You have a student house with K rooms, and a list of N students that applied for a room (a room takes only one student). Each candidate has a list of students he can't be with in the same house.

Implement an algorithm that, given K (the number of rooms in the house), a list of students that applied for a room, and a list of incompatibility between students, then find a list of students that can't be in the house due to being in a incompatibility list of a student in the house.

Sorry if it's already been asked, but I can't find it anywhere!

1

There are 1 answers

0
Stefan Schröder On BEST ANSWER

Look at assignment problem

and

stable roomates problem.

Addition: In regards to your question, search for the problem first and then choose an algorithm that fits your needs most. Normally, there are a number of algorithms to solve such problems you describe.