The Movie Scheduling _Problem_

Question

Currently I'm reading "The Algorithm Design Manual" by Skiena (well, beginning to read)

He asks a problem he calls the "Movie Scheduling Problem":

Problem: Movie Scheduling Problem

Input: A set I of n intervals on the line.

Output: What is the largest subset of mutually non-overlapping intervals which can be selected from I?

Example: (Each dashed line is a movie, you want to find a set with the highest quantity of movies)

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

The algorithm I thought of to solve it was like this: I could throw out the "worst offender" (intersects with the most other movies) until there are no worst offenders (zero intersections). The only problem I see is that if there is a tie (say two different movies each intersect with 3 other movies) could it matter which one I throw out?

Basically I'm wondering how I go about turning the idea into "math" and how to prove it correct/incorrect.

Answer 1

The algorithm is incorrect. Let's consider the following example:

Counterexample

           |----F----|       |-----G------| 

        |-------D-------|  |--------E--------|

|-----A------|    |------B------|    |------C-------|

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

Firstly, let's count, 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 a run of your algorithm. In the first step we delete B because it intersects with the most number of invervals and we get:

           |----F----|       |-----G------| 

        |-------D-------|  |--------E--------|

|-----A------|                      |------C-------|

It's 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 from {A, D, F} and at most one from {G, E, C}, to get the total of 2, which is smaller than the size of {A, B, C}.

The conclusion is, that after deleting B which intersects with the most number of invervals, you can't get the maximum number of nonintersecting movies.

Correct solution

The problem is very well known and one solution is to pick the interval which ends first, delete all intervals intersecting with it and continue until there are no intervals to examine. This is an example of a greedy method and you can find or develop a proof that it's correct.

Answer 2

This looks like a dynamic programming problem 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 may be more than one movie that starts at the same 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 a movie m from next(t) and compares the largest possible sets that either include or don't include m.

Invoke sched with the time of your first movie and you will get the size of the optimal set. Getting the optimal set itself just requires a little extra logic to remember which movies you select at each invocation.

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

It's correct, but I'd have to consult my algorithms textbook to give you an explicit proof, but hopefully this algorithm makes intuitive sense why it is correct.