A cleaning task for a group of busy roommates Been pondering on this question. I came up with a brute force algorithm that goes through each person and work one by one, which gave me a $O(n^2)$ time. However I was wondering if there is a way using  graphs and network flow for this question?
Suppose there are  roommates sharing an apartment. Over the next  weeks, each person is supposed
to clean the shared washroom exactly once so that someone different cleans each week.
Due to scheduling constraints (midterms, homework, etc.), each person is unable to clean on certain
weeks. Suppose the people sharing the apartment are labeled {1, 2, … , 
} and the weeks are labeled
{1, 2, … , 
}.
Then, for each person 
there is a set of weeks  ⊆ {1, 2, … , 
} where 
is unable to clean.
A feasible cleaning schedule is an assignment of each person sharing the apartment to a different
week, so that each person cleans on exactly one week, there is someone cleaning each week, and if
 cleans on week 
then  ∉ 
.
Describe an algorithm to determine if there is a feasible cleaning schedule or not. What is the running
time of your algorithm?
 A: I guess you could turn it into a flow problem if you transform it into a graph with a starting node that goes into n nodes which represent the roommates. 
The ending node would be connected to a set of n nodes that represent each week.
Then, connect each roommate's node to each node representing a week that they CAN clean. Now, if you assume each edge has weight one, the solutions will be any configuration that gives the maximum flow through the graph (assuming all edges have either 1 or 0 flow, not like 1/2).
This is because max flow would imply that all of the nodes representing each week have flow going to the ending node (or as many as possible), and all nodes representing a person have flow from the starting node.
A: Note that we are talking here about an instance of Hall's Marriage Theorem. The necessary and sufficient condition for the existence of a solution is the following: To any $k$-subset of the $n$ weeks there are at least $k$ roommates willing to clean in every one of these weeks. I'm writing this because you might find material concerning your problem under the heading Marriage Theorem.
