Reputation: 537
Question:
Find the minimum number of airplanes required for an airplane operator,given schedule of all flights.
So given a schedule (source, destination, departure time, duration of journey) of all flights, we need to find minimum number of airplanes the operator need.
When an airplane completes a trip. It takes at least 50 mins to start another trip.
Edit: I was unable to come up with a solution..
I tried making a graph with each trip as a node..and there is a directed edge between first node to second node if destination of first node is same as source of second node and start time of second node is 50 mims after completion of journey of first node.
any help would be appreciated on how to proceed..
Note: I was asked this question at an interview at Microsoft.
Upvotes: 3
Views: 381
Reputation: 2101
If I undestood you right, there are start city, finish-city, and we need to find way with minimum flights to reach destination city from start city. Is that ok?
How I see solution with dynamical programming, lets in dp[i][j]
will be stored best time we can get to reach city with number i
using only j
flights.
At beginning all elements of dp
is set to infinity
. We will try to update it on each step.
So, algorithm will be smth like this below :
dp[0][0] = 0;
priority_queue< pair<int,int> > q;
q.Add( make_pair(0,0) );
/*in q we store pair, where first is time of arrival in city,
and the second is THAT city.*/
while there are element is queue {
x = the first one element ( where time is the smallest )
remove first element from queue
if x.city == destination city
break cycle;
then
for all j
if dp[x.city][j] < x.time + 50
for all flights(from, to) where from==x.city we try to update
if( dp[to][j+1] < dp[x.city][j] + 50 + jurney_duration ) {
dp[to][j+1] = dp[x.city][j] + 50 + jurney_duration ;
q.add( make_pair(dp[x.city][j] + 50 + jurney_duration, to) );
}
}
so, to find answers, we only need to find the smallest x
where dp[final_dest][x] != infinity
, and this x
will be the answer.
The efficiency will be O(n*n*m)
, because the body of while-cycle
we will run only n
times ( where n - number of cities
), and cycle has two cycles of n
and m
.
We will run first for-cycle
only n times, because the path will use less than N
flights - there are no reason to get back to city where you was before.
EDIT:
Actually, if we will store information of flights like Adjacency list we can get efficiency even better : O(n*m), because, for example, if city with number i
is adjacent to mi, we will get N*m0 + N*m1 + ... + N*mN = N*(m0 + m1 + ... + mn) = N*M, because sum of mi th == M. (M stands for the total number of flights).
More details about priority queue
Upvotes: 1
Reputation: 2579
As the question is stated, it's actually pretty straightforward.
Order the flight list by the departure time.
Start with 0 planes.
For every flight,
look if there's a plane available at the source at the time of departure
If yes, select it, else add a new plane and select it.
Mark the plane as available at the destination at time of arrival + preparation
Return # of planes used
Upvotes: 0