shlogg · Early preview
Prashant Mishra @prashantrmishra

Optimizing Railway Platform Allocation With O(nlogn) Time Complexity

Min platforms required at railway station: O(nlogn) time complexity. Sort trains by arrival & departure times to minimize platform usage.

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 ascend...