content: package math;
  
  import java.util.Arrays;
  
  public class MinimumPlatforms {
  
      /*
       * Given arrival and departure times of all trains that reach a railway station,
       * find the minimum number of platforms required for the railway station so that no train waits.
       *
       * 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}
       * Output: 3
       *
       *
       * */
  
      static int findPlatform(int arr[], int dep[], int n) {
  
          // Sort arrival and departure arrays
          Arrays.sort(arr);
          Arrays.sort(dep);
  
          /* plat_needed indicates number of platforms
           *  needed at a time
           */
          int plat_needed = 1, result = 1;
          int i = 1, j = 0;
  
  
          /* Similar to merge in merge sort to process
           * all events in sorted order
           */
          while (i < n && j < n) {
  
              /* If next event in sorted order is arrival,
               * increment count of platforms needed
               * */
  
              if (arr[i] <= dep[j]) {
                  plat_needed++;
                  i++;
  
  
                  if (plat_needed > result)
                      result = plat_needed;
              }
  
              /*
               * Else decrement count of platforms needed
               * */
              else {
                  plat_needed--;
                  j++;
              }
          }
  
          return result;
      }
  
  
      public static void main(String[] args) {
          int arr[] = {900, 940, 950, 1100, 1500, 1800};
          int dep[] = {910, 1200, 1120, 1130, 1900, 2000};
  
          int n = arr.length;
          System.out.println("Minimum Number of Platforms Required = " + findPlatform(arr, dep, n));
      }
  }
  