3

質問：

すべてのフライトのスケジュールが与えられた場合に、飛行機のオペレーターに必要な飛行機の最小数を見つけます。

したがって、すべてのフライトのスケジュール (出発地、目的地、出発時刻、旅行期間) が与えられた場合、オペレーターが必要とする飛行機の最小数を見つける必要があります。

飛行機が旅行を完了するとき。次の旅行を開始するには、少なくとも 50 分かかります。

編集：解決策を思いつくことができませんでした..

各トリップをノードとしてグラフを作成してみました..最初のノードの目的地が2番目のノードのソースと同じで、2番目のノードの開始時間が旅の完了後50分である場合、最初のノードから2番目のノードの間に有向エッジがあります最初のノードの。

続行する方法について助けていただければ幸いです..

注: Microsoft でのインタビューで、この質問をされました。

4

2 に答える 2

1

私があなたを正しく理解していないとしたら、出発都市と目的都市があり、出発都市から目的地の都市に到達するには、最小限のフライトで道を見つける必要があります。それは大丈夫ですか？

動的計画法で解決策をどのように見るか、フライトのみを使用dp[i][j]して数字で都市に到達できる最適な時間を保存します。最初は、 のすべての要素が に設定されています。各ステップでそれを更新しようとします。したがって、アルゴリズムは次のようになります。ijdpinfinity

    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) );
                      }
              }

xしたがって、答えを見つけるには、最小のwhereを見つけるだけでよくdp[final_dest][x] != infinity、これxが答えになります。

O(n*n*m)の本体は( where ) 回while-cycleだけ実行され、cycle には と の 2 つのサイクルがあるため、効率は になります。最初に n 回だけ実行します。これは、パスがフライトより少ない回数しか使用しないためです。前にいた都市に戻る必要はありません。nn - number of citiesnmfor-cycleN

編集: 実際には、Adjacency listのようなフライトの情報を保存すると、効率がさらに向上します: O(n*m)。たとえば、番号のある都市がm iiに隣接している場合、N*m 0が得られるためです。 + N*m 1 + ... + N*m N = N*(m 0 + m 1 + ... + m n ) = N*M、m i th == Mの合計(M はフライトの総数）。 プライオリティ キューの詳細

于 2013-01-15T18:41:13.003 に答える
0

質問が述べられているように、それは実際にはかなり簡単です。

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

ノート

  • このアルゴリズムでは、飛行機がスケジュールに記載されている以外のフライトを行うことはできません。それが私が質問を理解している方法です。それが許されれば、この貪欲な解決策はもはや機能しません。
  • 現実世界の状況とはかけ離れているため、これは簡単です。たとえば、価格と容量が問題に導入された場合、問題はさらに複雑になります。
于 2013-01-15T14:19:12.357 に答える