K站台能容纳的列车的最大限值

Question

给定到达火车站的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}执行任务，因为这段时间没有发生其他火车。

Answer 1

在我看来(我没有严格的证据)贪婪的算法应该有效：

1. 按发车时间对火车进行排序。
2. 让我们维护一个大小为lastDeparture的数组k，其中lastDeparture[i]是最后一列火车离开i平台的时刻(最初充满了零)。
3. 让我们遍历trains数组并执行以下操作：

- Find all such platforms that `lastDeparture[i] <= currentTrain.arrival`.
- If there are no such platforms, continue.
- Otherwise, choose the one with the largest `lastDeparture` value(if there are several such platforms, we can pick any of them).
- increase the answer by one and add the current train to this platform(that is, assign `lastDeparture[i] = currentTrain.departure`.

​

证据的草图：

让我们假设我们的解不是最优的。让我们找出第一列火车是在我们的答案，但不是在最优的。应该有别的火车来代替它。但出发时间更长了。因此，当我们换乘这两列火车时，总数就不能增加。

时间复杂性：O(n log n)(步骤3可以使用一个平衡的二叉树来有效地处理，该树保持平台按照上一次出发时间排序)。

Answer 2

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

蛮力：

1. 合并和排序到达和离开(但保持跟踪哪是哪一列，并确定哪一列火车到达/离开)。
2. 遍历数组，为每次到达添加一个计数器，并在每次出发时减去一个。
3. 如果柜台为k，列车到达时，请取消在“溢出”到达时时间最长的车站的列车，离开了。注:这可能是到达的列车或已经在站台上的列车。
4. 答案是列车总数减去被取消的列车数量。

请注意，通过取消在站台上剩时间最长的车站上的火车，我们取消了最少的列车数。我们不得不取消车站的一列火车来释放一个月台，剩下时间最多的火车有最大的潜力为未来的到达者腾出空间。

这将是O(N*K)的复杂性，在最坏的情况下，如果给出到达和离开的排序，并可以迅速地一起。我注意到给出的例子几乎是这样的。

复杂性是排序和O(N*K)计数的最坏情况。

Answer 3

如果我正确地理解了这个问题，我相信这可以通过使用一个堆栈大小的k来完成，它将包含当前在一个平台上的列车。每列列车(按出发时间排序)：

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)，因为每列火车最多只能进入/离开堆栈一次。