Minimum Platforms Problem
You'll learn how to find the minimum number of railway platforms needed at a station by cleverly tracking overlapping train schedules.
The Core Idea
Imagine you're managing a train station. Trains arrive and depart throughout the day, and you need to figure out the minimum number of platforms required so no train is left waiting. The key insight? Sort arrivals and departures separately, then walk through time tracking how many trains are present simultaneously.
How It Works
Instead of pairing each arrival with its specific departure, treat all arrivals and all departures as independent sorted lists. Use two pointers to simulate time moving forward:
- Sort arrival times in one array
- Sort departure times in another array
- Start with both pointers at the beginning
- Walk through time:
- If next event is an arrival: a train enters (need one more platform)
- If next event is a departure: a train leaves (free up one platform)
- Track the maximum platforms needed at any moment
Why This Greedy Approach Works
By processing events in chronological order (greedy choice), we're always making the locally optimal decision. When trains overlap in time, we count them. The maximum overlap tells us the minimum platforms needed—we can't do better than accommodating the worst-case simultaneous arrivals.
This is similar to the Activity Selection and Meeting Room problems you've seen, but here we're counting maximum overlaps rather than selecting non-overlapping intervals.
Example Walkthrough
Arrivals: [9:00, 9:40, 9:50]
Departures: [9:10, 10:00, 11:00]
At 9:40, all three trains overlap briefly—you need 3 platforms minimum.
Key Takeaway: The Minimum Platforms Problem uses a greedy two-pointer technique on sorted arrival and departure times to find the maximum number of simultaneous trains, which equals the minimum platforms required.