Movie Planning _Problem_

Question

I am currently reading Leken’s Algorithm Design Guide (well, starting to read)

He poses a problem, which he calls the "Movie Tasks":

Problem: Movie Planning Problem

Input: set i of n intervals on the line.

Conclusion: what is the largest subset of mutually non-overlapping intervals that can be selected from I?

Example: (Each dotted line is a movie, you want to find the set with the most movies)

----a--- -----b---- -----c--- ---d--- -----e--- -------f--- --g-- --h-- 

The algorithm I decided to solve was as follows: I could throw out the “worst offender” (intersects with most other films) until there are no worst offenders (zero intersections). The only problem I see is that if there is a tie (say, two different films, each of which intersects with three other films), can this have the meaning that I chose?

I’m mostly interested in how I’m going to turn an idea into “mathematics” and how to prove it is right / wrong.

Answer 1

The algorithm is incorrect. Consider the following example:

Counterexample

  |----F----| |-----G------| |-------D-------| |--------E--------| |-----A------| |------B------| |------C-------| 

You can see that there is a solution of at least 3 in size, because you can pick A, B and C

First, let the calculation for each interval the number of intersections:

 A = 2 [F, D] B = 4 [D, F, E, G] C = 2 [E, G] D = 3 [A, B, F] E = 3 [B, C, G] F = 3 [A, B, D] G = 3 [B, C, E] 

Now consider the launch of your algorithm. In the first step, we will remove B because it intersects with the largest number of inversions and we get:

  |----F----| |-----G------| |-------D-------| |--------E--------| |-----A------| |------C-------| 

It is easy to see that now from {A, D, F} you can choose only one, because each pair intersects. The same case with {G, E, C} , so after deleting B you can choose at most one of {A, D, F} and at most one of {G, E, C} to get a total of 2 , which smaller than {A, B, C} .

The conclusion is that after removing B , which intersects with a large number of intervals, you cannot get the maximum number of disjoint films.

Correct solution

The problem is very well known, and one solution is to select the interval that ends first, delete all intervals intersecting with it and continue until the intervals are detected. This is an example of a greedy method, and you can find or develop proof of its correctness.

Answer 2

This looks like dynamic programming to me:

Define the following functions:

 sched(t) = best schedule starting at time t next(t) = set of movies that start next after time t len(m) = length of movie m 

next returns a set because there can be more than one movie at a time.

then sched should be defined as follows:

 sched(t) = max { 1 + sched(t + len(m)), sched(t+1) } where m in next(t) 

This recursive function selects the movie m from next(t) and compares the largest possible sets that include or do not include m .

Call sched with the time of your first movie, and you will get the size of the optimal set. Getting the optimal set just requires a bit of extra logic to remember which movies you choose with each call.

I think this recursive (as opposed to iterative) algorithm works in O (n ^ 2) if you use memoization, where n is the number of movies.

That's right, but I would have to consult a tutorial on my algorithms to give you explicit evidence, but hopefully this algorithm makes an intuitive sense of why it is correct.

Answer 3

 # go through the database and create a 2-D matrix indexed a..h by a..h. Set each # element of the matrix to 1 if the row index movie overlaps the column index movie. mtx = [] for i in range(8): column = [] for j in range(8): column.append(0) mtx.append(column) # b <> e mtx[1][4] = 1 mtx[4][1] = 1 # e <> g mtx[4][6] = 1 mtx[6][4] = 1 # e <> c mtx[4][2] = 1 mtx[2][4] = 1 # c <> a mtx[2][0] = 1 mtx[0][2] = 1 # c <> f mtx[2][5] = 1 mtx[5][2] = 1 # c <> g mtx[2][6] = 1 mtx[6][2] = 1 # c <> h mtx[2][7] = 1 mtx[7][2] = 1 # d <> f mtx[3][5] = 1 mtx[5][3] = 1 # a <> f mtx[0][5] = 1 mtx[5][0] = 1 # a <> d mtx[0][3] = 1 mtx[3][0] = 1 # a <> h mtx[0][7] = 1 mtx[7][0] = 1 # g <> e mtx[4][7] = 1 mtx[7][4] = 1 # print out contstraints for line in mtx: print line # keep track of which movies are still allowed allowed = set(range(8)) # loop through in greedy fashion, picking movie that throws out the least # number of other movies at each step best = 8 while best > 0: best_col = None best_lost = set() best = 8 # score if move does not overlap with any other # each step, only try movies still allowed for col in allowed: lost = set() for row in range(8): # keep track of other movies eliminated by this selection if mtx[row][col] == 1: lost.add(row) # this was the best of all the allowed choices so far if len(lost) < best: best_col = col best_lost = lost best = len(lost) # there was a valid selection, process if best_col > 0: print 'watch movie: ', str(unichr(best_col+ord('a'))) for row in best_lost: # now eliminate the other movies you can't now watch if row in allowed: print 'throwing out: ', str(unichr(row+ord('a'))) allowed.remove(row) # also throw out this movie from the allowed list (can't watch twice) allowed.remove(best_col) # this is just a greedy algorithm, not guaranteed optimal! # you could also iterate through all possible combinations of movies # and simply eliminate all illegal possibilities (brute force search)