问题：
给定所有航班的时间表（起点、终点、出发时间、旅行持续时间），找到一个航空公司所需的最少飞机数量。
当一架飞机完成一次旅行后，需要至少50分钟才能开始另一次旅行。
编辑：我无法想出解决方案...
我尝试将每次旅行作为一个节点构建图表...如果第一个节点的目的地与第二个节点的源相同，并且第二个节点的开始时间比第一个节点的旅行时间晚50分钟，则两个节点之间存在有向边。
非常感谢您提供任何帮助和指导。
注意：我在微软面试中被问到了这个问题。
返回结果：如果我理解正确，有起始城市、目的地城市，我们需要找到最少航班的方式从起始城市到达目的地城市。这样可以吗？
我认为使用动态规划的解决方案，让 dp[i][j] 存储我们只使用 j 次航班就能到达编号为 i 的城市的最佳时间。
一开始，dp 的所有元素都设置为 无穷大。我们将在每个步骤中尝试更新它。
因此，算法将类似于以下内容：
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，其中dp[final_dest][x]！= infinity，这个x将是答案。
效率将为O(n*n*m)，因为while-cycle的主体只运行n次（其中n-城市数量），而循环有两个循环n和m。
我们将仅运行第一个for-cycle n次，因为路径将使用少于N次航班 - 没有理由回到之前所在的城市。
编辑：
实际上，如果我们像邻接表一样存储航班信息，我们可以获得更好的效率：O(n*m)，因为例如，如果编号为i的城市与mi相邻，我们将获得N*m0+N*m1+...+N*mN=N*(m0+m1+...+mn)=N*M，因为mi的总和==M（M表示航班总数）。
有关优先队列的更多详细信息
正如问题所述，它实际上非常简单。
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