Minimum Platforms

Intuition

Sort arrivals and departures separately. Use two pointers: for each arrival, if a train has departed by then, it frees a platform. Count max overlapping arrivals.

Algorithm

1Sort arr[] and dep[].
2i=1, j=0, platforms=1, maxPlatforms=1.
3While i<n and j<n: if arr[i]<=dep[j]: platforms++; i++. Else: platforms--; j++.
4maxPlatforms=max(maxPlatforms,platforms).
5Return maxPlatforms.

Example Walkthrough

Input: arr=[0900,0940,0950,1100,1500,1800], dep=[0910,1200,1120,1130,1900,2000]

1.Sorted. At 0940: 3 trains (0940,0950 arrived, 0910 departed by 0950). Peak=3.

Output: 3

Common Pitfalls

•Sort BOTH arrays independently â€” the i-th arrival does not correspond to the i-th departure after sorting.

Minimum Platforms.java

Java

// Approach: Event sweep. Sort arrivals and departures separately; sweep to find peak simultaneous trains.
// Time: O(n log n) Space: O(1)
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[]) {
        int a[] = new int[2360];
        for (int i = 0; i < arr.length; i++)
            a[arr[i]]++;

        for (int i = 0; i < arr.length; i++) {
            if (dep[i] + 1 < a.length)
                a[dep[i] + 1]--;
        }

        int t = 0, ans = 0;
        for (int i = 0; i < a.length; i++) {
            t += a[i];
            ans = Math.max(ans, t);
        }

        return ans;
    }
}

Was this solution helpful?