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;
}
}
Top comments (0)