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.

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.

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

### 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 thatno 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

## No comments:

## Post a Comment