Minimum Platforms Problem

Geeks for Geeks [Medium]

Problem Statement

Find minimum number of platforms required at a railway station so that no train waits.

Example: Arrival = [9:00,9:40,9:50], Departure = [9:10,12:00,11:20] → Output: 2

Approach 1: Brute Force

Check for each train the number of overlapping trains.

for each train i:
    count = 1
    for each other train j:
        if i and j overlap:
            count++
    maxPlatforms = max(maxPlatforms, count)
return maxPlatforms

💡 Think: Count overlaps for each train and track the worst-case simultaneous count.

Approach 2: Better

Sort arrival and departure, for each arrival count overlaps.

sort arrivals
sort departures
platforms = 1
for i=1 to n:
    if arrival[i] <= departure[j]:
        platforms++
    else:
        j++
return max platforms

💡 Think: Sort arrivals/departures; increment on arrival, decrement on departure, track max.

Approach 3: Optimal Greedy

Two-pointer method on sorted arrivals and departures.

sort arrivals
sort departures
i = j = 0, platforms = 0, result = 0
while i < n:
    if arrival[i] <= departure[j]:
        platforms++
        i++
        result = max(result, platforms)
    else:
        platforms--
        j++
return result

💡 Think: Walk arrivals and departures with two indices; current platforms reflects active trains.

Solve on LeetCode