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:, 3:[4, 3], 4:[4, 3] --> Yes # possible 1:[1, 3, 2], 2:, 3: --> 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[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: 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,), (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.
Just do it. Write a backtracking algorithm that assigns people to seats and returns true/false if everyone can be seated. Test it on small inputs to check it’s correct. Then try it on the large input. Optimise as required.
Ideas for optimisations:
- Assign fussy people (who have a small number of preferences) first.
- Hall’s Marriage Theorem gives a necessary and sufficient condition for a bipartite matching to exist from people to seats. All groups of people must between them like a number of seats greater than or equal to their own number. Obviously, the sufficient condition is too slow to check (there are 2**n subsets), but you can improve the backtracking algorithm by regularly testing the necessary condition on the people remaining to be seated and the seats untaken.This reduces the search space by dismissing branches earlier.
Tried it on the website. Backtracking algorithm scored 80. Scored 100 after making the second optimisation (regularly checking Hall’s condition)