DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Minimum number of platforms required

Problem
TC: O(nlogn)

class Solution { // Function to find the minimum number of platforms required at the // railway station such that no train waits. static int findPlatform(int arr[], int dep[]) { //sort the trains on the basis of arrival time of each train PriorityQueue<Schedule> q = new PriorityQueue<>((a,b)-> a.a-b.a); for(int i =0;i<arr.length;i++){ q.add(new Schedule(arr[i],dep[i])); } //sort the trains on the basis of which train will leave first once they have  //been arrived (which is done on the basis of ascending order of depart time of the trains) Queue<Integer> trackDepart = new PriorityQueue<>(); int noOfplatform = 1;// at min we will need 1 platform while(!q.isEmpty()){ Schedule s = q.remove();// train arrived  if(!trackDepart.isEmpty()){ if(trackDepart.peek() < s.a){ // if the arrival time of the train is greater than the  //train that will depart first then new train can arrive on the same platfrom (no increment in the platfrom no.) trackDepart.remove(); // old train will go } else{ noOfplatform++;// else new train will need to come in a different platform } } trackDepart.add(s.d);// add the depat time of the new train the queue to check for the next train if that can arrive on the same of new platform will be needed  } return noOfplatform; } } class Schedule{ public int a; public int d; public Schedule(int a, int d){ this.a = a; this.d= d; } } 
Enter fullscreen mode Exit fullscreen mode

Top comments (0)