-1

Let's say Mr. A goes to cinema and he gets a movie schedule. There are N movies on the program today (1 < N < 50) and for every movie the time of the start and the time of the end are given in minutes. Mr. A wants to see as much minutes of movies as possible. But, there is one rule in the cinema: If a movie starts, you can't watch it. In other word if Mr. A watches Movie 1 and in meantime Movie 2 starts, Mr. A can't watch it. Find the maximum number of minutes that Mr. A can spend watching movies.


At first I sorted the movies according to their starting time. Then I made a NxN matrix and fill it with false values. Now if Movie X and Movie Y intersect, i.e play in the same time even just for a minute, then Matrix[X][Y] and Matrix [Y][X] get true value. Then I check the case when every movie is in the optimal solution. I put them into vector. Now using recursion I check every possible combination. If Movie X doens't have an intersection with every movie of the vector, I put into the vector, since there will be no intersection and then I move on to the next movie. And so on.

This algorithm works, but I think that it's too much time-consuming and as I want to say it's "modified brute-force". Is there any better way to reach the optimal solution.

NOTE: We are interested only about the maximum numbers of minutes, not in the maximum number of movies. At the end the program should print the maximum number of minutes, not a list of the movies Mr. A should watch.

  • Hint: Work backwards. If he arrives at the end of the night, he can watch zero minutes. Going back in time one minute at a time, the minutes he can watch is the w[t] = max(w[t+1], w[t+m[i]]+m[i]) where i iterates over the movies starting at time t. w[t] is the number of minutes he can watch when arriving at time t, and m[i] is the length of movie i. – Sjoerd Mar 21 '14 at 14:11
1

Sounds like a decision tree to me.

Make a graph.

Start with a root node, then for its children list all the movies that A could watch first.

For each child, store the length of the movie and add nodes for each movie that A could watch after that child's movie ends. (i.e., you step out of theater 7 at 10:02 am and check the other 49 theaters to see which ones are not currently playing a movie. Add them as child nodes).

Continue until you read end of day / your graph is fully populated.

Now search your graph for the path with the highest collective minutes (i.e., the sum of minutes for each movie in the path). There are several well known algorithms for doing this. DFS comes to mind for me, but I think there are better ones.

---------edit----------

Excellent comment from AMADANON Inc:

You might improve this alogrithm - do breadth first search, and at any time when two or more branches are NOT watching a movie at the same time, all except the one with the most minutes watched so far can be eliminated (in the case of a tie in the number of minutes, all but an arbitrarily chosen one in the tie can be eliminated). This will save lots of processing during the short film festival.

(Comments are sometimes lost, so I'm putting it here)

  • 1
    You might improve this alogrithm - do breadth first search, and at any time when two or more branches are NOT watching a movie at the same time, all except the one with the most minutes watched so far can be eliminated (in the case of a tie in the number of minutes, all but an arbitrarily chosen one in the tie can be eliminated). This will save lots of processing during the short film festival. – AMADANON Inc. Mar 21 '14 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.