Skiena Design by Algorithm

Question

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

5-18. Consider the set of films M_1, M_2, .. M_k. There are many clients, each of which points to two films that they would like to see this weekend. Films are shown on Saturday evening and Sunday evening. You can watch several movies at the same time. You have to decide which films should be broadcast on Saturday and Sunday so that each client finds out about the two films they want. Is there a schedule when each movie is displayed no more than once? Create an efficient algorithm to find such a schedule, if one exists.

Solution: We have a set {M1, M2..Mk} for films and a set {C1, C2, .. Cp} for clients. We connect to the edges of the 2 films that C1 wants to watch, connect to the edges of the 2 films that C2 wants to watch, etc. A set of films becomes a related schedule. I want to check if this is a bipartite graph, such as 2 favorite films, cannot be shown on the same night (color 2 selected films with different colors). If this is the case, we show all films painted in 1st color on Saturday and 2nd color on Sunday. The problem is resolved. But in case this is not what I should do?

Answer 1

The question mentions that we can show films at the same time. Take two sets and the Sun. For each client, check whether the films that he wants to see will be in different sets, if they do not fit randomly in the SB and one in the Sun continues. If they are in one set, put any of them in another set. In the worst case, each film will be shown both on the satellite and on the Sun.

Answer 2

Create a timeline from the films M1, M2, ..., Mk. If Mi and Mj are specified by the client, we put a line between Mi and Mj. Repeat this for all customers. Then use the two-color algorithm to divide the films into two groups: one is Saturday and the other is Sunday.