Minimum Number of Platforms
Given train arrival and departure times, find the minimum platforms so no train waits.
Open on GeeksforGeeks ↗Intuition
The answer is the maximum number of trains present at once. Sort arrivals and departures separately and sweep: an arrival is +1 platform, a departure is −1. The peak of that running count is the answer.
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
Separate the two event streams
Platform need only changes at an arrival or a departure — sort each list and merge-walk them chronologically.
Sweep with a counter
If the next arrival is ≤ the next departure, a train arrives before any leaves: need += 1. Otherwise one leaves: need -= 1. Track the max.
Why ≤ matters
If a train arrives exactly when another departs, both briefly need platforms — count the arrival first.
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.