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

别墅里的技校生

您将获得列车到达特定车站的到达和出发时间。您需要在任何时候找到火车所需的最小站台数量。
例如：
arrival[] = {1:00，1:40，1:50，2:00，2:15，4:00}departure[] = }No. of platforms required in above scenario = 4请注意，到达时间按时间顺序排列。
; H9 b' W! ?$ [# [+ W3 T; F7 r0 Z                                                               
$ S& }9 ^  ?# ~5 r! [8 R    解决方案:                                                               
) R  i% G, |" }; w3 l                                                                解决方案1：
您可以迭代所有间隔，并检查有多少其他间隔与之重叠，但这将需要 o(N^2) 时间复杂度。
! S- T  T# T$ L4 @& R( M) s解决方案2：
/ j: C6 ~: M' g# q' w: Z  h9 L我们将使用与合并排序非常相似的逻辑。
对到达（arr）和离开（dep）数组进行排序。
. c3 P- a# |) p5 C$ p6 m- H- I比较到达和离开数组中的当前元素，并在两者中选择较小的元素。
如果元素从到达数组中提取，则添加 platform_needed。
% E( ]8 {' S  Q若元素出发数组中提取元素，则减少 platform_needed。
0 Y" B1 l3 V- I( v: V在执行上述步骤时，我们需要跟踪 platform_needed 最大值的计数。
1 A1 Y: y0 y  Y最后，我们将返回 platform_needed 达到最大值。时间复杂：O(NLogN)
下图将使您更好地理解上述代码：
# _2 {# k$ p, `. Z
   
火车站所需平台数量最少的平台Java程序
4 u, _5 i) f: c; ]. s9 s6 b# Y+ qTrainPlatformMain.java
package org.arpit.java2blog;import java.util.Arrays;public class TrainPlatformMain    public static void main(String args[])           // arr[] =        dep[] =     int arr[] =     int dep[] =     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  maxPlatforms)                     maxPlatforms = platform_needed;                                     else                                                                                                                                                                                                                                  platform_needed--;                j  ；                               return maxPlatforms;   当您操作上述程序时，您将获得以下输出：
Minimum platforms needed: