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.

Sprain

how long is a movie? – Biddable

@Biddable each movie is an hour, so you don't need to worry if you watch a movie at 14:00, you may miss the one at 15:00. Great question! – Sprain

Looks like a maximum matching problem on a bipartite graph. – Dollar

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.

Warrantee

I like this aproach, but still - maximum flow algorithm has huge complexity. – Elayneelazaro

@Elayneelazaro What do you mean by "huge complexity"? If you use Hopcroft-Karp you can get worst-case O(M*sqrt(N)) where M is the number of edges and N is the number of nodes (in this case, number of movies + number of different times); this will run under a second for thousands of movies + times. Moreover, many flow algorithms are heavily influenced by the structure of the network and can run much faster in many cases. Finally, the OP asked for something better than backtracking. – Warrantee

I'm not very familiar with maximum flow algorithm, so I'll need to spend a bit more time to learn it before I reply you.. But it's great to know there exist this algorithm with better complexity. Thanks! – Sprain

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.

Dollar

Answer 3

WHILE list of movie times isn't empty 
    1. Sort movie showtime list in order of the number of showtimes.
    2. Watch next movie according to this sort at the first available time.
    3. Remove respective time from each movie showtime list and movie 
       from the movie list.

Python attempt:

A=[15,'A']
B=[14,15,17,'B']
C=[15,17,'C']
D=[15,20,'D']

movies=[A,B,C,D]


watchOrder = []

def f(x):
    while x: # while x isnt empty
        x=sorted(x, key=len)
        watchOrder.append(x[0])
        r = x[0][0]
        x.remove(x[0])
        for l in x:
            if r in l:
                l.remove(r)
f(movies)
print(watchOrder)

Mayes

Unfortunately this can fail to find a solution even though one exists. For a counterexample, see the counterexample I give to a very similar solution to an equivalent problem here: https://mcmap.net/q/1317249/-generating-a-basic-school-schedule – Peacock