Java 程序计算火车站所需的最少站台数

火车站问题 是编码面试中最重要的题目之一，通常用于测试候选人的逻辑能力和问题解决能力。

火车站问题

在这个问题中，提供了火车站列车的到站和离站时间。有两个名为 arrival[] 和 departure[] 的数组，分别表示列车的到达和离开时间（24小时制）。我们必须找出车站所需的最小平台数，以便列车能够按计划运行。

让我们通过一个例子来理解这个问题。

示例 1

输入： arrival[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}

departure[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

输出 3

在同一时间（11:00 至 11:20 之间），最多有三列火车。因此，我们至少需要三个平台，否则火车站将无法为所有火车提供平台。

让我们看另一个例子。

示例 2

输入: arrival[] = {09:10, 01:00}

departure[] = {09:50, 01:30}

在上面给出的修剪中，第一列火车于上午 10:20 到达，于上午 10:50 离开。现在，该平台没有分配给任何火车。因此，我们只需要一个平台来分配火车。

问题的解决方案

以下是找出所需最小平台数的两种可能解决方案：

• 朴素方法
• 高效方法

朴素方法

这是找出火车站所需最小平台数的最简单方法。该解决方案可以通过使用两个嵌套的 for 循环来实现。

内部 for 循环用于计算与外部 for 循环表示的区间相交的区间数。内部循环执行结束后，更新计数的最大值。之后，继续外部 for 循环的下一次迭代。当外部循环退出时，我们就得到了计数的最大值。这就是火车站所需的平台数。

上述方法的 time complexity 为 O(n²)，space complexity 为 O(1)，因为没有使用额外的空间。

算法

让我们在 Java 程序中实现上述方法。

Platform.java

输出

Minimum number of Platforms required: 3

我们可以通过使用贪婪且高效的方法来优化上述解决方案。

高效方法

首先，我们将到达和离开时间的所有数组进行排序。排序逻辑使得计算已到达但尚未离开的火车数量变得容易。

问题是如何找出某一时刻所需的平台总数。我们可以通过找出那一时刻到达和离开时间之间的差值来找出平台总数。上面计算出的所有时间的最大值将是最终答案。在下面的程序中，我们检查了以下两个必要条件：

1. if(arrival[i]<=departure[j]) 表示需要一个额外的平台。增加计数并增加 i。
2. if(arrival[i]>departure[j]) 表示我们有一个多余的平台。我们必须释放该平台以供其他即将到达的火车使用。为此，我们减少计数变量但增加变量 j。在 while 循环的每次迭代之后，更新答案为 max(result, count)。

在上述方法中，我们使用排序来对火车的到达和离开时间进行排序，这需要 O(logn) 时间。此外，我们遍历数组，这需要 O(n) 时间。因此，整体 time complexity 为 O(nlogn)。该方法不使用任何额外空间，因此 space complexity 为 O(1)。

RailwayStation.java

输出

Minimum Number of Platforms Required = 1

我们观察到，火车站所需的最小平台数等于火车站任何给定时间可能存在的最大火车数量。

结论

朴素方法相当复杂，程序的执行 complexity 为 O(n²)，而高效方法则相对更优化，time complexity 为 O(nlogn)。