Minimum Number of Platforms
Given train arrival and departure times, find the minimum platforms so no train waits.
- 1 <= n <= 10⁵
- 0000 <= arrival[i], departure[i] <= 2359 (24-hour times)
- A train arriving exactly as another departs still needs its own platform
Intuition
The minimum number of platforms problem gives arrival and departure times for trains at a station and asks how many platforms are needed so that no train ever waits. The reframing that solves it: the answer is the maximum number of trains present at the station simultaneously. If four trains overlap at some instant, four platforms are required; if never more than two overlap, two suffice. So the question becomes finding the peak of a count over time. That count only changes at two kinds of moment — an arrival adds a train, a departure removes one. Nothing happens in between, so there is no need to simulate time continuously. Sort the arrivals and the departures into two separate lists and walk them in chronological order, adjusting a counter: - An arrival is +1, a departure is −1, and the running maximum is the answer. Note that the two lists are sorted independently. It does not matter which train each time belongs to — only that a train arrived or departed — which is why pairing them is unnecessary and would only get in the way. One tie-break decides correctness. If a train arrives at exactly the moment another departs, both need a platform at that instant, because the departing train has not physically cleared yet. So when the next arrival time is less than or equal to the next departure time, process the arrival first.
The key move is refusing to think in trains and thinking in events instead. Sorting arrivals and departures independently breaks the pairing — which is fine, because the peak occupancy doesn't care which train is which, only how many are inside at once. Any "maximum concurrent X" problem yields to this sweep: +1 on each start, −1 on each end, track the running peak.
Approach
Before reading on: price up what the direct approach costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n log n) time and O(1) space.
Reframe as the peak of overlapping trains
Platforms needed equals the largest number of trains present at once. This turns a scheduling question into finding a maximum, which is what makes the sweep possible.
Sort arrivals and departures separately
Sort each list on its own; the pairing between a train's arrival and its departure is irrelevant. All that matters is the chronological sequence of events, and separating them is what lets a simple two-pointer merge walk that sequence.
Sweep both lists with two pointers
Compare the next arrival against the next departure and process whichever comes first. Advance only that pointer. The sweep visits every event exactly once in time order without ever building a merged list.
Increment on arrival, decrement on departure
An arrival raises the running count and a departure lowers it. Update the maximum after each increment — that peak is the answer, and it is the only value that needs to survive the sweep.
Break ties in favour of the arrival
When arrival time is less than or equal to departure time, count the arrival first. A train arriving exactly as another leaves still needs its own platform at that instant. Using a strict < here undercounts by one on inputs with touching times, which is the classic failure case.
Cost of the sweep
Sorting the two lists dominates at O(n log n), after which the sweep is a single O(n) pass. Space is O(1) beyond the sorting, since only two pointers, a counter and a maximum are kept.
Solution & live demo
Common pitfalls
Keeping arrival and departure paired
trains = sorted(zip(arr, dep)) for a, d in trains: ...
arr.sort(); dep.sort()
while i < len(arr):
if arr[i] <= dep[j]: need += 1; i += 1
else: need -= 1; j += 1Keeping pairs forces you to ask which specific train left, which needs a heap or a scan. Sorting the two lists separately turns the problem into a merge of timestamps — the only question left is whether the next event is an arrival or a departure.
Using < and freeing the platform too early
if arr[i] < dep[j]:
if arr[i] <= dep[j]:
A train arriving at the exact minute another departs cannot reuse the platform — both occupy it at that instant. Strict < treats the slot as already free and undercounts by one on touching times.
Recording the peak only at the end
while i < len(arr):
...
return need ...
best = max(best, need)
return bestneed is the current occupancy, which falls back toward zero as trains leave. The answer is the highest it ever reached, so the maximum must be sampled after every arrival.
Edge cases
Tie processed as arrival first → correctly demands an extra platform.
Counter climbs to n and never drops until the end.