Q:

A solution to a Graph algorithm required

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.

A:

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

