CODEWITHSUNDEEP
algorithmgraph
abhinav
abhinav

Reputation: 537

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.

Upvotes: 3

Views: 381

Answers (2)

ivan.mylyanyk
ivan.mylyanyk

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

voidengine
voidengine

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

Notes

  • This algorithm doesn't allow planes to make another flights than those in the schedule, that's how I understand the question. If that were allowed, this greedy solution wouldn't work anymore.
  • This is easy because it's far from a real world situation. If e.g. price and capacity are introduced to the problem, it gets much trickier

Upvotes: 0

Related Questions