In need of a Greedy Algorithm

[neutrino86]

I have no clue on how to do this, besides the use of a brute force algo.

 

Given a single aircraft to start with, an airline company decides to start a contract based rent-a-plane business...

Given the starting and ending time of the contract offered by the would be passengers, and the cost they are willing to bear, develop an algorithm to decide which contracts to take, keeping in mind, that the highest amount of profit is to be developed.

The contracts can be contiguous in their periods.

The number of contracts which can be given as input can be upto 100000 in number. So time is a constraint with the algorithm.

 

Please share your ideas.

[neutrino86]

umm....In case any of you missed this thread...Here it is again...

 

 

Given a single aircraft to start with, an airline company decides to start a contract based rent-a-plane business...

Given the starting and ending time of the contract offered by the would be passengers, and the cost they are willing to bear, develop an algorithm to decide which contracts to take, keeping in mind, that the highest amount of profit is to be developed.

The contracts can be contiguous in their periods.

The number of contracts which can be given as input can be upto 100000 in number. So time is a constraint with the algorithm.

 

 

please share your ideas...

[lwebzem]

I would first build the graph for all possible contacts and then apply dynamic programming.

 

Here is the first step:

 

Input data in the form for each contract ordered by starttime

START_TIME END_TIME COST id

 

 

N number of contracts

 

FOR i=1 TO N

END_NODE= True

MIN_END_TIME=99999

FOR j=i+1 TO N

 

IF MIN_END_TIME <= START_TIME(j) THEN

EXIT FOR 'we are done for node i

ELSE

IF END_TIME(j) < MIN_END_TIME THEN

MIN_END_TIME=END_TIME(j)

END IF

END IF

IF START_TIME(j) >= END_TIME(i) THEN

W(i,j)=Cost(i)

END_Node=False

END IF

 

 

NEXT

IF END_Node=True then ' I am adding the end node so

' all paths will be finished in this node

W(i,N+1)=0

END IF

NEXT

 

 

' Now adding the start node

FOR i=1 to N

W(0,i)=Cost(i)

NEXT

 

 

' So the weight for link from START node to node 1 is the cost of contract 1

' the weight for link from node 4 to node 5 is the cost of contract 5 and so on....

 

 

Now I believe we can apply the dynamic programming to find path from START node to END node

with max sum of weight whict will be prophit or cost from contracts. It will be similar

to finding shortest path algorithm.

[neutrino86]

hmmm...i'll think about it a bit... i am not in friends with dynamic programming right now.

Thankyou for your effort.