Skiena Design on Algorithm

Question

I am stuck on a problem in Skiena's Design on Algorithms.I don't know if my solution is right.

5-18. Consider a set of movies M_1, M_2,.. M_k. There is a set of customers, each one of which indicates the two movies they would like to see this weekend. Movies are shown on Saturday evening and Sunday evening. Multiple movies may be screened at the same time. You must decide which movies should be televised on Saturday and which on Sunday, so that every customer gets to see the two movies they desire. Is there a schedule where each movie is shown at most once? Design an efficient algorithm to find such a schedule if one exists.

Solution: We have a set {M1,M2..Mk} for movies and a set {C1,C2,..Cp} for costumers.We connect with an edge 2 films that C1 desires to watch,connect with an edge 2 movies that C2 wants to watch and so on.The set of movies become a connected graph.I want to verify if it is a bipartite graph such as 2 favorite movies could not be showed in the same night(color 2 favorites movies with different colors).If it is,we show all the movies colored with 1st color on Saturday and 2nd color an Sunday.problem solved.But in case it isn't what should I do?

Answer 1

Create a graph from movies M1, M2, ..., Mk. If Mi and Mj is indicated by a customer, we put an edge between Mi and Mj. Repeat this for all customers. Then use two-color algorithm to bipartite movies into two sets, one is Saturday and the other is Sunday.

Answer 2

The question mentions that we can show movies at the same time. Take two sets Sat and Sun. For each customer check if the movies he want to see are in different sets, if they aren't put one at random in Sat and one in Sun and continue. In case they are in the same set, put any one of them in the other Set. In worst case each movie will be shown on both Sat and Sun.