<分区>
给定到达火车站的 N 列火车的到达和出发时间，对于给定的 k 平台，返回我们可以在 k 上容纳的最大火车数量平台。
k <<< N
到达和离开时间数组
Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
这个问题是在一些采访中问到我的，那么最好的算法是什么？这个问题是从这个问题稍微修改的。
我尝试了这个问题的贪心算法，但它不适用于所有测试用例。 例如:对于 k=2 我们有时间间隔
arr[]={1:00,1:30,2:00}
dept[]={1:40,2:10,3:30}
' 删除 {1:30 和 2:10 间隔我们可以完成 k=2 的任务 {1:00-1:40} 和 {2:00-3:30} 因为这段时间之间没有其他火车出现
最佳答案
在我看来(我没有严格的证明)贪心算法应该有效:
按出发时间对火车进行排序。
让我们维护一个数组 lastDeparture尺寸k , 其中lastDeparture[i]是末类车离开i的时间平台(最初用零填充)。
让我们遍历 trains 数组并执行以下操作:
找到所有这样的平台 lastDeparture[i] <= currentTrain.arrival .
如果没有这样的平台，继续。
否则，选择lastDeparture最大的一个值(如果有多个这样的平台，我们可以选择其中一个)。
将答案加一，将当前列车加入该站台(即分配lastDeparture[i] = currentTrain.departure。
证明草图:
让我们假设我们的解决方案不是最优的。让我们找到在我们的答案中但不在最佳答案中的第一列火车。应该有其他火车代替它。但它的出发时间更长。因此，当我们交换这两列火车时，总数不会增加。
时间复杂度:O(n log n) (第 3 步可以使用平衡二叉搜索树有效地处理，该树使平台按最后出发时间排序)。
关于arrays - k站台可容纳的最大列车数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28705374/