0

I was asked this question in my interview. I know that on StackOverflow, we are not supposed to ask for direct answers for the i/w questions. So instead of that, I would to ask for correct approach/hint to solve it

I have been given two array of movie starts times and end times.

int start[], int end[]

For these two arrays, I have to find the max movies I can watch. In my opinion, this is the exact opposite of the problem, where we have to find the max overlap for given intervals.

My approach was this, if for any movie, there is no overlap, we should watch it. However, if there is a overlap and the other overlap is of shorter duration then discard this movie else take this movie.

This algorithm fails this dataset

movie 1:4,8 movie 2 :6,11 movie 3:2,5

This algorithms correctly eliminates 4,8 as 2,5 is more desirable. However, it eliminates 6,11 in favor of 4,8 even though that is something we have already eliminated and it should be considered.

May I know what is the correct approach to solve this problem?

Community
  • 1
  • 1
Max
  • 9,100
  • 25
  • 72
  • 109
  • *then discard this movie else take this movie* How are you ever going to solve a serious programming problem if you (try to) use the same pointer (that's what the word `this` is in English) to different objects (the two different movies). Your question is confusing to me. – High Performance Mark Jul 11 '14 at 17:37
  • 1
    Sounds like a variation of a typical resource-allocation algorithm. Plenty of material can be found on the [Wikipedia page](http://en.wikipedia.org/wiki/Knapsack_problem#Solving) – blgt Jul 11 '14 at 17:37
  • same question with all possible solutions ....http://www.codechef.com/problems/HOTEL :p – Nullpointer Jul 11 '14 at 17:37
  • 1
    Seems like this could be interval scheduling. – harold Jul 11 '14 at 17:37
  • possible duplicate of [Maximum non-overlapping intervals in a interval tree](http://stackoverflow.com/questions/19850580/maximum-non-overlapping-intervals-in-a-interval-tree) – Sergey Kalinichenko Jul 11 '14 at 17:38
  • There is a good pseudo-polynomial algorithm for this. See the linked question that I think is an exact duplicate with different wording. – Sergey Kalinichenko Jul 11 '14 at 17:39
  • Possibly this: http://www.cs.illinois.edu/class/fa07/cs473ug/Lectures/lecture2.pdf – Ben Jul 11 '14 at 17:40
  • Agree with @blgt. You need to choose items from set of items and maximize value of function (number of videos). But you have a constraint - selected video shouldn't overlap. – ceth Jul 11 '14 at 17:41

1 Answers1

3

You can prove a greedy selection property for this problem. Namely, assume you have an optimal solution (max number of movies) and consider the first movie. If there is another movie that you didn't select that has an ending time earlier than the ending time of the first selected movie, then you can swap the first selected movie with that movie that has the earliest ending time and still have a valid optimal solution. Thus, you sort movies by their ending times, and start by choosing the movie with the earliest ending time and then you iteratively choose the movie with the earliest ending time that does not overlap with the previously selected movie. This gives an O(n log n) time algorithm if you include time for sorting, and it's linear time O(n) after you sort.

user2566092
  • 4,631
  • 15
  • 20
  • I think I've heard this explanation before and accepted it then, but now something's off. _"If there is another movie that you didn't select that has an ending time earlier than the ending time of the first selected movie, then you can swap the first selected movie with that movie that has the earliest ending time and still have a valid optimal solution."_ If you can swap a current selection with a movie that has an earlier ending time, you said it's still a valid solution, but can you explain why it's MORE optimal? – Ben Jul 11 '14 at 18:23
  • It's not more optimal, it's just as optimal as the original optimal solution. But the point is that the argument shows you can safely choose the first movie to be the movie with the earliest ending time, and get an optimal solution. This allows you to find ONE optimal solution quickly. There can be other optimal solutions too. – user2566092 Jul 11 '14 at 18:27
  • Nice solution. I was thinking of a DP solution but that would cost more time and space. – HelloWorld123456789 Jul 11 '14 at 18:31