Watch all movies algorithm

Question

I came across this problem which seems pretty interesting. There are a few movies that we want to watch all of them but they only show at the following times:

movieA : 15
movieB : 14, 15, 17
movieC : 15, 17
movieD : 15, 20

We can watch A at 15, B at 14, C at 17 and D at 20, so it's possible to watch them all. Note that you can't watch C at 15, not viable.

The problem as you have guessed, is whether we can watch them all.

Obviously we can solve it with backtracking, trying all possibilities. Is there better way to do it? I have an idea of starting with movies with least number of available times first, that way we can find the solution faster if there's a solution, the worst case time complexity is still the same.

Is there a better algorithm for this problem out there?

P.S. As @gen asked, I forgot to point out that each movie is 1 hour, so if you watch one at 14:00, you won't miss the one at 15:00. Thanks for asking.

Answer 1

Depending on the bounds on the number of movies and number of possible different times for each movies, you could create a bipartite graph with the movies in one side and the times in the other side and run a maximum flow algorithm to determine the maximum matching. If movie i can be watched at time j, then add an edge between the corresponding nodes in the graph.

Answer 2

Looks like a maximum matching problem on a bipartite graph. The vertices of the graph are the two independent sets 'hours of the day' and 'film titles'. The edges of the graph are showings of a particular film at a particular time.

According to Steven Skiena's Algorithm Design Manual, the best known algorithm is the Hopcroft-Karp algorithm which runs in O(E*sqrt(V)). E is the number of edges, ie. the number of showings. V is the number of vertices, ie. the number of films plus the number of distinct hours during which films are shown. In your example, E = 8 showings, V = 4 films + 4 distinct times = 8.

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Note the matching formulation is only possible because your films all start on the hour and last exactly one hour. They either exactly coincide, or don't overlap at all.