Movie Scheduling Problem

Last night one of mine coding friend thrown a problem on me, & he called it as movie scheduling problem, He wanted me to develop a algo & code for this.

The Problem

Let x be a super-star
Let n be a Producer

n Producers wanted to cast x in there upcoming movie, and for that they are offering the same amount to x but the start & end date interval of each movie making process is different for eg. 1 movie require 10 months to complete whereas other require 1.5 yrs, now the algo. has to decide which movie x will do such that x will make the highest profit.

The criteria for job acceptance is clear: 

x want to make as much money as possible. Because each of these films pays the same fee

per film, this implies x seek the largest possible set of jobs (intervals) such that
no two of them conflict with each other.


I come up with 3 Algo's lets go through it one by one ...

ALGO 1: Earliest Job 1st

Suppose x don't have any work so he will select a movie which ever comes first
but this algo will not make the highest profit bcoz if actor select the 1st movie and the 2nd to 5th movie offers are such that the total time period require to complete all 4 movies is equal to time require to complete 1st movie.
So here the total loss is of 4 movies...


ALGO 2: Smallest Job 1st

This algo is better than the previous one bcoz it will give decent solution.

ALGO 3: Earliest Completion Date

This algo. gives optimal solutions for most of the possible inputs ...

I have coded the solution for Algo 3 whose output looks like ...

The Output
--------------------------------------------------------------------------------------------------------------
The output is a 4 dimension array where
0th column gives movie name
1st column gives start date
2nd column indicates end date
3rd column indicates status P or F , such that P indicate, the no. of movies has to be accepted by x to earn the maxm profit.

Download