k站台可容纳的最大列车数

Question

给定到达火车站的 N 列火车的到达和出发时间，对于给定的 k 站台，return 我们可以在 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}

这个问题是在一些采访中问到我的，那么最好的算法是什么？这个问题是从这个问题稍微修改的。

我尝试了这个问题的贪婪算法，但它不适用于所有测试用例。对于 eg:for 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} 因为这段时间之间没有其他火车

Answer 1

我想我之前误解了这个问题。如果我们的站台数量有限，我认为我们现在被要求取消最少数量的列车，这样时间表就不会压垮站台。

暴力破解：

合并和排序到达和离开（但跟踪哪个是哪个并识别哪个火车arrives/departs）。
遍历数组，每次到达时向计数器加一，每次离开时减一。
如果计数器是 k 并且有火车到达，取消在 'overflowing' 时间站台上 left 时间最长的火车到达。注意：这可能是到达的火车或已经在站台上的火车。
答案是列车总数减去取消的列车数。

请注意，通过在站台上剩余时间最长的车站取消火车，我们取消了最少数量的火车。我们必须在车站取消一列火车以释放站台，剩余时间最多的站台最有可能释放 space 以供将来到达。

如果对到达和离开进行排序并且可以快速拼凑在一起，那么在最坏的情况下这将是 O(N*K) 的复杂度。我注意到给定的例子几乎是这样。

复杂度是排序的最坏情况，O(N*K) 计算。

Answer 2

如果我对问题的理解正确，我相信这可以通过使用大小为 k 的 stack 来完成，它将包含当前在站台上的火车。对于每列火车（按出发时间排序）：

while current.ArrivalTime > stack.Last.DepartureTime:
  remove the top element (train) from the stack
push the current train IF there is room, else ignore it
answer = max(answer, stack.Size)

您的堆栈达到的最大大小就是问题的答案。

由于排序原因，这应该是 O(n log n)，因为每列火车最多进入/离开堆栈一次。

Answer 3

在我看来（我没有严格的证明）贪心算法应该有效：

按出发时间排序。
让我们维护一个大小为k的数组lastDeparture，其中lastDeparture[i]是最后一班火车离开i站台的时间（最初用零填充）。
让我们遍历火车数组并执行以下操作：
- 找到所有这样的平台 lastDeparture[i] <= currentTrain.arrival.
- 如果没有这样的平台，继续。
- 否则，选择lastDeparture值最大的那个（如果有多个这样的平台，我们可以选择其中一个）。
- 将答案加一，将当前列车加入该站台（即赋值lastDeparture[i] = currentTrain.departure.

证明草图：

让我们假设我们的解决方案不是最优的。让我们找到在我们的答案中但不在最佳答案中的第一列火车。应该有其他火车代替它。但它的出发时间更长。因此，当我们交换这两列火车时，总数不会增加。

时间复杂度：O(n log n)（第 3 步可以使用平衡二叉搜索树有效地处理，该树使平台按最后出发时间排序）。

k站台可容纳的最大列车数

Maximum no of trains that k platform can hold

arrays

algorithm

dynamic-programming

greedy

data-structures