Minimum Platforms

You are given the schedule of trains at a station as a list trains, where each train is [arrival, departure]. A platform can hold only one train at a time, and if one train arrives at the exact moment another departs they still need separate platforms.

Return the minimum number of platforms required so that no train ever has to wait.

Hints

· Stuck? Reveal one nudge at a time.

How many platforms do you need at any single instant?

It's the maximum number of trains at the station at the same time — peak interval overlap.

Sort arrivals and departures separately and sweep them together, +1 on an arrival, -1 on a departure.

Common doubts

You only need the count of overlapping intervals over time, not which train is which. Two sorted event lists reproduce the timeline of arrivals and departures exactly.

A train arriving at the same instant another departs still overlaps it (they can't share a platform), so an equal-time arrival must be counted before the departure frees a platform.

The count only ever increases on an arrival, so any maximum is reached immediately after some arrival event — which is why the brute checks arrival times.

Interview follow-ups

· What an interviewer asks next.

Track the event times as you sweep; record the interval during which the running count equals the peak.

That becomes a scheduling/feasibility problem — with k platforms you'd greedily assign arrivals to freed platforms via a min-heap of departure times.

Fun facts

This is the interval-graph chromatic number in disguise: the minimum platforms equals the maximum clique of overlapping intervals, which for intervals equals the peak overlap.
The same sweep counts peak concurrent connections on a server or peak simultaneous calls in a phone network.

Asked at

AmazonGoogleMicrosoftGoldman Sachs

Frequently Sometimes Occasionally

Example 1

Input: trains = [[900,910],[940,1200],[950,1120],[1100,1130],[1500,1900],[1800,2000]]
Output: 3
Between 950 and 1120, trains [940,1200], [950,1120], and [1100,1130] overlap — three platforms are needed.

Example 2

Input: trains = [[1,2],[3,4]]
Output: 1
The two trains never overlap, so a single platform suffices.

Constraints

- 1 <= trains.length <= 10^5 - trains[i] == [arrival_i, departure_i] with arrival_i <= departure_i

The number of platforms you need at any instant is just the number of trains currently at the station — the peak overlap of all the [arrival, departure] intervals. Find that peak efficiently by merging the arrival and departure timelines.

Prerequisites

Before you start

· Concepts used directly in the solution.

Sweep line. Counting how many intervals are active as you move a pointer along time.

Two pointers. Merging two sorted sequences (arrivals and departures) in lockstep.

Interval overlap. A platform is occupied for the whole [arrival, departure] window, endpoints inclusive.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“If a train arrives exactly when another departs, can they share a platform?”

No — the arrival counts as overlapping the departure, so they need separate platforms.

“What am I computing?”

The maximum number of trains present at the station at the same time.

The data

“Are arrivals and departures paired?”

Each train has its own arrival and departure, but for the count you can sort the two lists independently.

The ideal opening — say it like this

The answer is the maximum number of trains at the station at once — the peak interval overlap.

I'll sort arrivals and departures separately and sweep them together.

Each arrival before the next departure needs a new platform; each departure frees one. I track the running peak.

Understand the problem

Worked example — arrivals 900 940 950 1100 1500 1800, departures 910 1120 1130 1200 1900 2000

900 arrive  -> 1   950 arrive -> 3 (peak)   1500 arrive -> 2
910 depart  -> 0.. wait, merge in sorted order:
running count peaks at 3 while trains 940, 950, 1100 overlap
answer: 3

Key observations

1Aha

Answer = peak overlap of the intervals

A platform is busy for a train's whole [arrival, departure] window. The minimum platforms is the maximum number of these windows overlapping at any instant.

2Aha

Sort arrivals and departures separately

You don't need to keep trains paired to count overlaps. Two sorted timelines — one of arrivals, one of departures — let you replay events in time order.

3Aha

Arrival before departure means overlap

When the next arrival is <= the next departure, a train enters before one leaves, so the count rises. The <= (not <) enforces that same-instant arrive/depart still need two platforms.

Brute force vs optimal

	Count at each arrival	Merge two timelines
Idea	For each arrival time, count trains present	Sweep sorted arrivals and departures with two pointers
Time	O(n^2)	O(n log n)
Space	O(1)	O(n)

The peak overlap always occurs at some arrival, so the brute checks each; the two-pointer sweep finds the same peak in one merged pass. Full code is in the Approaches selector below.

Summary

Key takeaway

Minimum platforms = peak number of trains at the station at once. Sort arrivals and departures separately and sweep with two pointers: each arrival that comes before the next departure adds a platform (track the running peak), each departure frees one. O(n log n).

sort arrivals; sort departures
platforms = 0; peak = 0; i = j = 0
while i < n:
    if arr[i] <= dep[j]: platforms += 1; i += 1; peak = max(peak, platforms)
    else:                platforms -= 1; j += 1
return peak