GeeksforGeeks Medium

Minimum Number of Platforms

Given train arrival and departure times, find the minimum platforms so no train waits.

greedysortingtwo-pointers

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.

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

python

▶1def min_platforms(arr, dep):
▶2    arr.sort(); dep.sort()
▶3    i = j = need = best = 0
▶4    while i < len(arr):
▶5        if arr[i] <= dep[j]:
▶6            need += 1; i += 1
▶7        else:
▶8            need -= 1; j += 1
▶9        best = max(best, need)
▶10    return best

Edge cases

Arrival equals a departure time

Tie processed as arrival first → correctly demands an extra platform.

All trains overlap

Counter climbs to n and never drops until the end.

Complexity

Time

O(n log n)

Space

O(1)

Two sorts + linear merge sweep.

← Prev · GFG

Maximum Sum Increasing Subsequence

Next · GFG →

Morris Inorder Traversal