Suppose you and your friend Alanis live, together with n?2 other people for a to
ID: 3708423 • Letter: S
Question
Suppose you and your friend Alanis live, together with n?2 other people for a total of n, at a popular off-campus cooperative apartment, the Upson Collective. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so that someone cooks on each of the nights.
Of course, everyone has scheduling conflicts with some of the nights (e.g., exams, concerts, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, lets label the people {p1,...,pn} and the nights {d1,...,dn}. For person pi, theres a set of nights Si ? {d1,...,dn} when they are not able to cook.
Explanation / Answer
The algorithm is as follows:
We have set of n people and set of nights for each person on which they can not cook.We will
start with night1 and can check all the people one by one by checking if he/she is free on
that night by considering their respctive set of nights in which they are not available.
So for every night we need to process each person's set of nights. Assuming each person
is not available for an average of m nights, then for every night we need to consider
n * m options (where n is the number of persons) in the worst case. We have n nights so
the order of complexity is n * (n *m) which O(n^2*m)