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)