Minimum Platforms

Given arrival and departure times, find the minimum number of platforms so no overlapping trains share one. Sort arrivals and departures separately, then merge-walk both timelines: an arrival before the next departure needs a new platform; a departure frees one.

Category: Greedy
Time complexity: O(n log n)
Space complexity: O(1)

Pseudocode

sort arrivals[], departures[] separately
merge-walk both with two pointers
arrival ≤ next departure: platforms += 1 (track max)
else: platforms -= 1

Reference implementation

arrivals.sort(); departures.sort()
i = j = platforms = max_platforms = 0
while i &lt; n and j &lt; n:
    if arrivals[i] &lt;= departures[j]:
        platforms += 1; max_platforms = max(max_platforms, platforms); i += 1
    else:
        platforms -= 1; j += 1

Open the interactive Minimum Platforms visualisation →