Find Minimum Platforms Required

Title: Find Minimum Platforms Required

Scheduling problems show up constantly in interviews, and the minimum platforms problem is one of the most common ones you will see for railway or airport style scheduling. Given the arrival and departure times of a set of trains, the goal is to find the smallest number of platforms that lets every train arrive and depart without ever waiting for a free platform. In this guide, you will learn a clean O(n log n) approach using sorting and a two-pointer scan, see a full Java program, walk through the algorithm step by step, and look at the edge cases an interviewer expects you to catch.

Understanding the Problem

You are given two arrays, arrivals and departures, where the i-th train arrives at arrivals[i] and leaves at departures[i]. Both times belong to the same train and use the same time format, for example HHMM style values like 900 for 9:00 AM. A platform can only serve one train at a time, so if two trains are at the station simultaneously, each one needs its own platform.

The task is to compute the minimum number of platforms needed so that no train ever has to wait for a platform to become free. This is really asking for the maximum number of trains that overlap at any single point in time, since that peak is exactly how many platforms must exist.

Algorithm Steps

The key insight is that you do not need to track individual trains at all, only the running count of trains currently at the station. Sorting the arrival and departure times independently turns the problem into a simple merge.

1. Copy the arrivals and departures arrays into sortedArrivals and sortedDepartures so the original input is not mutated.
2. Sort sortedArrivals and sortedDepartures independently with Arrays.sort. Each array becomes its own timeline of events; the sorted index no longer identifies which train an event belongs to.
3. Initialize platformsNeeded and maxPlatforms to 0, and two pointers, i for arrivals and j for departures, both starting at 0.
4. Loop while both i and j are within bounds, comparing the next unprocessed arrival to the next unprocessed departure.
5. If sortedArrivals[i] <= sortedDepartures[j], a train arrives before or at the same time as the next train leaves, so increment platformsNeeded and advance i.
6. Whenever platformsNeeded rises above maxPlatforms, update maxPlatforms to the new value.
7. Otherwise, the next event is a departure, so decrement platformsNeeded and advance j.
8. Continue until every arrival has been processed, then return maxPlatforms as the answer.

Once every arrival has been processed, platformsNeeded can no longer increase, so maxPlatforms is already the final answer by the time the loop exits.

Java Program

Here is a complete, compilable Java program that implements the approach above.

import java.util.Arrays;

public class MinimumPlatforms {

    public static int findMinimumPlatforms(int[] arrivals, int[] departures) {
        int n = arrivals.length;
        int[] sortedArrivals = arrivals.clone();
        int[] sortedDepartures = departures.clone();
        Arrays.sort(sortedArrivals);
        Arrays.sort(sortedDepartures);

        int platformsNeeded = 0;
        int maxPlatforms = 0;
        int i = 0;
        int j = 0;

        while (i < n && j < n) {
            if (sortedArrivals[i] <= sortedDepartures[j]) {
                platformsNeeded++;
                i++;
                if (platformsNeeded > maxPlatforms) {
                    maxPlatforms = platformsNeeded;
                }
            } else {
                platformsNeeded--;
                j++;
            }
        }

        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};

        int result = findMinimumPlatforms(arrivals, departures);
        System.out.println("Minimum platforms required: " + result);
    }
}

Explanation of the Program

Walking through the code line by line:

• findMinimumPlatforms clones the input arrays with clone() before sorting, so the caller’s original arrivals and departures arrays are left untouched.
• Arrays.sort(sortedArrivals) and Arrays.sort(sortedDepartures) turn the two arrays into independent, ordered timelines of arrival events and departure events.
• The while loop merges the two timelines one event at a time, similar to merging two sorted lists, except here each comparison decides whether a platform is gained or freed.
• platformsNeeded tracks how many trains are at the station right now; maxPlatforms remembers the highest value it has ever reached.
• The loop stops as soon as every arrival has been consumed, since at that point platformsNeeded can no longer increase.

Step-by-Step Trace

To see the two pointers in action, trace the algorithm on five trains with arrival times [10, 15, 20, 35, 48] and matching departure times [40, 25, 45, 50, 60]; after sorting both arrays independently, the algorithm should report that 3 platforms are required.

At the end of each iteration, platformsNeeded holds the number of trains simultaneously at the station at that point in time, and maxPlatforms holds the largest value platformsNeeded has reached so far, which is exactly the answer once the loop finishes.

Examples

Example 1: Mixed Overlapping Schedule

Six trains with a mix of overlapping and non-overlapping windows, taken directly from the main method above.

int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
int result = findMinimumPlatforms(arrivals, departures);
// result is 3

Example 2: Fully Overlapping Trains

Three trains that all arrive before any of them departs, so every train needs its own platform at the same time.

int[] arrivals = {1000, 1005, 1010};
int[] departures = {1030, 1035, 1040};
int result = findMinimumPlatforms(arrivals, departures);
// result is 3 (all three trains overlap)

Example 3: Fully Sequential Trains

Three trains that each depart well before the next one arrives, so a single platform can serve all of them.

int[] arrivals = {900, 1000, 1100};
int[] departures = {930, 1030, 1130};
int result = findMinimumPlatforms(arrivals, departures);
// result is 1 (no two trains overlap)

Common Mistakes to Avoid

These are the mistakes that most often turn a correct idea into a wrong answer on this specific problem.

• Sorting only one of the two arrays – leaves the other array in its original per-train order, so the comparison between sortedArrivals[i] and sortedDepartures[j] no longer reflects two real event timelines. Sort arrivals and departures independently before the merge.
• Using < instead of <= – treats a train departing at the exact same minute another one arrives as if two platforms were needed at once, overcounting the result by one. Use <= so a departure frees its platform before or exactly when a new arrival needs one.
• Sorting the caller’s original arrays directly – calling Arrays.sort(arrivals) on the input mutates it in place, silently losing the original per-train arrival-departure pairing if the caller needed it later. Clone the arrays first, as findMinimumPlatforms does above.
• Assuming sortedArrivals[i] and sortedDepartures[i] belong to the same train – after independent sorting, index i in each array no longer identifies a specific train, only a position in that array’s own timeline. Treat the two sorted arrays purely as event streams, not per-train records.

Edge Cases to Test

An interviewer will expect you to call out these boundary inputs before being asked.

• Empty arrival/departure arrays
• Single train
• All arrivals at the same time
• All departures at the same time
• Departure and arrival tied at the same time
• Fully overlapping schedule
• Fully sequential schedule
• Mismatched array lengths

Additional Considerations

Time and Space Complexity

Sorting sortedArrivals and sortedDepartures costs O(n log n) each, and the merge style scan afterward only costs O(n), so the overall time complexity is O(n log n), dominated by the two sorts. Space complexity is O(n) for the two cloned arrays; if mutating the caller’s input is acceptable, you can sort arrivals and departures directly and drop the clone step to get O(1) extra space.

Alternative: Min-Heap of Departure Times

A second common solution sorts trains by arrival time only, then pushes each train’s departure time onto a min-heap. Before adding a new train, it pops any heap entries whose departure time is less than or equal to the new arrival time, since those platforms are now free. The heap size after each insertion is the number of platforms in use, and the overall complexity is still O(n log n). This version is worth knowing because it naturally extends to assigning an actual platform number to each train, which plain counting cannot do.

Interview Follow-up Questions

Once you have the base solution working, expect an interviewer to push further with questions like these.

• What if two trains have the same arrival or departure time? – trace through why <= already handles ties correctly, since a departing train frees its platform before or exactly when the new arrival needs one.
• What if you need to know which platform number each train is assigned to, not just the count? – switch to the min-heap approach, assigning the platform whose departure time is being popped to the new arrival.
• What if the schedule arrives as a continuous stream throughout the day instead of being known upfront? – maintain a min-heap of active departure times and add or remove platforms as each new event is observed in real time, since the full set of arrivals is never available to sort in advance.
• What if the arrival and departure arrays are read-only and billions of entries long? – process events from external sorted streams instead of sorting in memory, keeping only the running platformsNeeded and maxPlatforms counters in memory at any point.

Conclusion

The minimum platforms problem is a great example of how sorting plus a single linear scan can replace what looks at first like a scheduling simulation. Once you see the arrivals and departures as two independent timelines of events, the two-pointer merge falls out naturally, and the same pattern reappears in meeting-room scheduling and other resource-allocation problems.

Try adapting findMinimumPlatforms to also return the platform number assigned to each train using the min-heap variant described above. You can find more array based interview problems like this one in the Arrays category on this site.