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?
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.