Halodoc | Online Round | Maximum profit from selecting movies
Anonymous User
352

Can anyone suggest optimal solution for this problem <Time complexity O(n)>?

Imagine you are a highly-in-demand actor, who has been presented with offers to star in n different movie projects under development. 
Each offer comes specified with the first and last day of filming. To take the job, you must commit to being available throughout this entire period. 
Thus you cannot simultaneously accept two jobs whose intervals overlap.
For an artist such as yourself, the criteria for job acceptance is clear: you want to make as much money as possible. 
Each of these movies pays the same fee per movie.
Come up with an algorithm to help to choose r movies from n movies which maximize profit.

Input : {{2,5},{6,10},{7,15},{17,19},{20,24}}
Output : 4
Explanation - Can select 4 movies - {{2,5},{6,10},{17,19},{20,24}}
Comments (3)