How to seat everyone according to preferences?

Question

This problem is from CodeEval problem 118

Your team is moving to a new office. In order to make them feel comfortable in a new place you decided to let them pick the seats they want. Each team member has given you a list of seats that he/she would find acceptable. Your goal is to determine whether it is possible to satisfy everyone using these lists.

The seats in the new office are numbered from 1 to N. And the list of seating preferences each team member has given you is unsorted.

Example input and output:

1:[1, 3, 2], 2:[1], 3:[4, 3], 4:[4, 3] --> Yes # possible
1:[1, 3, 2], 2:[1], 3:[1] --> No # not possible

How to solve it?

---

What did I try? I believe the solution would be recursive, and this is what I have come up with so far, but I don't think I'm breaking down the problem correctly into its smaller subproblems.

def seat_team(num_seats, preferences, assigned):
    if len(preferences) == 1:
        for seat in range(len(preferences)):
            print preferences
            seat_wanted = preferences[0][1][seat]
            if not assigned[seat_wanted-1]:
                assigned[seat_wanted-1] = True
                return True, assigned
        return False, assigned
    else:
        for i in range(len(preferences)):
            current = preferences[i]
            for seat in current[1]:
                    found, assigned = seat_team(num_seats, [preferences[i]], assigned)
                    if not found:
                        return False
                    found, assigned = seat_team(num_seats, preferences[i+1:], assigned)
                    if not found:
                        return False
        return True

num_seats = 4
preferences = [(1,[1,3,2]), (2,[1]), (3,[4,3]), (4,[4,3])]
assigned = [False] * num_seats

print seat_team(4, preferences, assigned)

Any ideas? I'm sure that there's a generic name for this sort of problem, and an algorithm to solve it, but I haven't been able to find similar problems (or solutions) online. Please share examples if you know of any, I would really appreciate it.

Answer 1

This is a standard Maximum Bipartite Matching problem.

The set S represent M vertices, each belonging to a member and set T represent N vertices, each for a seat. There is edge from S_i to T_j if i^th member wants j^th seat. This is required bipartite graph. If maximum matching comes out to be M, then we have the solution else not.