Minimum Platforms Needed for Bus / Train

Minimum Platforms Needed for Bus / Train

  June 20, 2017    

---

Problem : Given arrival and departure times of all buses / trains that reach a station, find the minimum number of platforms required for the station so that no train/bus waits.

Tags : Minimum Platforms geeks solution in O(nlog n)

Explanantion : Sort both the arrays (departure / arrival) then we can easily check that if any vehicle need platform by checking arrival time and departure time of vehicle.

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG

 {

public static void main (String[] args)

{

Scanner ab=new Scanner(System.in);

int t=ab.nextInt();

while(t-->0)

{

   int i,n=ab.nextInt();

   int arr[]=new int[n];

   int dep[]=new int[n];

   for(i=0;i<n;i++)

   arr[i]=ab.nextInt();

   for(i=0;i<n;i++)

   dep[i]=ab.nextInt();

   Arrays.sort(arr);

   Arrays.sort(dep);

   int platform=1,need=1;

   i=1;

   int j=0;

   while(i<n && j<n)

   {

       if(arr[i]<dep[j])

       {

            platform++;

          i++;

          if (platform > need)  // Update result if needed

              need = platform;

      }

      else // Else decrement count of platforms needed

      {

          platform--;

          j++;

      }

       }

       System.out.println(need);

   }

}

}