3

问题：

给定所有航班的时间表，找出飞机运营商所需的最少飞机数量。

因此，给定所有航班的时间表（来源、目的地、出发时间、旅程持续时间），我们需要找到运营商所需的最少飞机数量。

当飞机完成一次旅行时。开始另一趟旅程至少需要 50 分钟。

编辑：我无法提出解决方案..

我尝试将每次旅行作为一个节点制作一个图。如果第一个节点的目的地与第二个节点的源相同，并且第二个节点的开始时间是旅程完成后的 50 分钟，那么第一个节点到第二个节点之间存在有向边的第一个节点。

任何帮助将不胜感激如何进行..

注意：我在微软的一次采访中被问到这个问题。

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

所以，要找到答案，我们只需要找到最小的xwhere dp[final_dest][x] != infinity，这x就是答案。

效率将是O(n*n*m)，因为while-cycle我们的主体只会运行n次数（ where n - number of cities），而循环有两个循环n和m。我们将for-cycle仅先运行 n 次，因为该路径将使用少于N航班 - 没有理由返回您之前所在的城市。

编辑： 实际上，如果我们将像邻接列表这样的航班信息存储起来，我们可以获得更好的效率：O(n*m)，因为例如，如果编号为 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 回答