Let\'s say Mr. A goes to cinema and he gets a movie schedule. There are N movies

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.