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.