DSA AnimatorDSA animations
Minimum Platforms GFG Medium Greedy · Sort + Two Pointers
Problem

Given arrival and departure times of trains at a railway station, find the minimum number of platforms required so that no train waits. Each platform holds one train at a time.

Example 1
arr[] = [900, 940, 950, 1100, 1500, 1800]
dep[] = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Example 2
arr[] = [900, 1100, 1235]
dep[] = [1000, 1200, 1240]
Output: 1
Constraints: 1 ≤ n ≤ 50,000  |  Times in HHMM format (e.g. 900 = 9:00 AM)
Try Examples
Custom (arrivals / departures):
Approach
Sort + Two Pointers — Sweep Arrival and Departure Events
Sort both arrays. At each step, whichever comes first (arrival or departure) is processed: +1 or -1 platforms. Track the peak.
Platform Sweep Arena
Arrivals arr[]
Departures dep[]
Current Decision
Waiting to start...
Time Comparison
arr[i]
—
vs
dep[j]
—
Platform Occupation
In use: 0  / Peak: 0
Variables
i (arrival ptr)
—
j (departure ptr)
—
plat (in use)
—
ans (peak)
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Sort arr[] and dep[] independently
2
i=1, j=0, plat=1, ans=1 — first train always needs a platform
3
arr[i] ≤ dep[j] → arrival first → plat++, i++
4
arr[i] > dep[j] → departure first → plat--, j++
5
ans = max(ans, plat) after every event
Time
O(n log n)
Space
O(1)
Why This Works

Sorting both arrays and sweeping them with two pointers simulates processing events in chronological order. When an arrival comes before the next departure, a platform must be acquired. When a departure comes first, one is freed. The peak simultaneous count is the answer — we never need more platforms than the most trains present at once.

How to solve Minimum Platforms

GFG · Medium · Greedy · Pattern: Sort + Sweep

Why the obvious approach is slow

Checking how many trains overlap each train is O(n²). We only care about the moments when trains come and go.

The key idea

Sort the arrival times and the departure times separately. Sweep through time with two pointers, and at each step take whichever event comes first. An arrival adds a platform and a departure frees one, so track the maximum in use.

Remember

Sort the events and sweep the timeline. The answer is the peak number of trains at the same time.

Run the animation above on your own input, or watch the 1:26 video explanation of Minimum Platforms with a dry run and Java code.

More Greedy problems