一个火车站所需的最少站台数量

Question

您将获得到达特定车站的列车的到达和出发时间。您需要找到在任何时间点容纳火车所需的最少站台数量。
例如：

arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00} 
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
No. of platforms required in above scenario = 4

请注意，抵达时间按时间顺序排列。

Answer 1

解决方案1：
您可以迭代所有间隔并检查有多少其他间隔与其重叠，但这将需要 o(N^2) 时间复杂度。

解决方案2：
我们将使用与归并排序非常相似的逻辑。

• 对到达（arr）和离开（dep）数组进行排序。
• 比较到达和离开数组中的当前元素并在两者中选择较小的一个。
• 如果元素是从到达数组中提取的，则增加 platform_needed。
• 如果元素是从出发数组中提取的，则减少 platform_needed。
• 在执行上述步骤时，我们需要跟踪达到 platform_needed 的最大值的计数。
• 最后，我们将返回 platform_needed 达到的最大值。

时间复杂度：O(NLogN)
下图会让你更好地理解上面的代码：

火车站所需平台最少数量的Java程序
TrainPlatformMain.java

package org.arpit.java2blog;

import java.util.Arrays;

public class TrainPlatformMain {
    public static void main(String args[])
    {
        // arr[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
        // dep[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}

        int arr[] = {100, 140, 150, 200, 215, 400};
        int dep[] = {110, 300, 210, 230,315, 600};
        System.out.println("Minimum platforms needed:"+findPlatformsRequiredForStation(arr,dep,6));
    }

    static int findPlatformsRequiredForStation(int arr[], int dep[], int n)
    {
        int platform_needed = 0, maxPlatforms = 0;
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i = 0, j = 0;

        // Similar to merge in merge sort
        while (i < n && j < n)
        {
            if (arr[i] < dep[j])
            {
                platform_needed++;
                i++;
                if (platform_needed > maxPlatforms) 
                    maxPlatforms = platform_needed;
            }
            else 
            {
                platform_needed--;
                j++;
            }
        }
        return maxPlatforms;
    }
}

当你运行上面的程序时，你会得到以下输出：

Minimum platforms needed:4