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.