Minimum Platforms

Minimum Platforms is a classic scheduling problem: given when every train arrives and leaves a station, how many platforms do you need so that no train is ever left waiting? It is the same shape as "how many meeting rooms do I need" — a greedy sweep over a timeline.

The slow way first

The brute-force idea: for each train, count how many other trains overlap with it in time, then take the worst case. Checking every pair of trains is O(n²) — fine for a handful of trains, too slow when there are many.

The better question: at any single instant, how many trains are present? The answer is just the number of platforms in use right then. We want the peak of that count over the whole day.

The idea: sweep the timeline

We do not need to track which train is which — only how the count rises and falls. Sort the arrivals and sort the departures separately. Then walk a clock forward: every arrival bumps the count up by one, every departure drops it by one. The highest the count ever reaches is the answer.

Two pointers i (into arrivals) and j (into departures) let us process the events in time order, like merging two sorted lists: whichever next event is earlier happens next.

The key insight: on a tie (an arrival time equals a departure time) we process the arrival first, since the two trains overlap at that instant and need separate platforms.

Walk through it

Step through the animation. The top row is the sorted arrivals, the bottom row the sorted departures. Pointer i advances on the top, j on the bottom. At each step we compare the cell under i with the cell under j: if the arrival is <= the departure, a train comes in (count goes up); otherwise a train leaves (count goes down). The running count and its max sit underneath. The count peaks at 3 around 9:00, and that peak is the final answer.

Pseudocode

sort arr ascending
sort dep ascending
platforms = 0, max_platforms = 0
i = 0, j = 0
while i < number of trains:
    if arr[i] <= dep[j]:
        platforms += 1                  # a train arrives
        max_platforms = max(max_platforms, platforms)
        i += 1
    else:
        platforms -= 1                  # a train departs
        j += 1
return max_platforms

The Python solution

def min_platforms(arr, dep):
    arr.sort()
    dep.sort()
    platforms = max_platforms = 0
    i = j = 0
    n = len(arr)
    while i < n:
        if arr[i] <= dep[j]:
            platforms += 1
            max_platforms = max(max_platforms, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return max_platforms

• We sort arr and dep independently — we only care about the order of events, not which train is which.
• i and j are two pointers walking the sorted arrival and departure lists.
• The loop runs while i < n. Once every arrival is processed, no count can ever rise again, so the peak is fixed.
• arr[i] <= dep[j] is the heart of the sweep: <= (not <) makes a tie count as an arrival first, so overlapping trains get separate platforms.
• Each arrival bumps platforms and refreshes max_platforms; each departure lowers platforms. We never need to lower i or revisit anything.

Complexity

Sorting is the bottleneck at O(n log n); the sweep itself is linear and uses only a couple of counters, so the extra space is O(1) beyond the input.

When this pattern shows up

Practice