DSA Tracker

Visualize

Minimum Platforms

Chronological sweep of arrivals and departures

time O(n log n)space O(n)

Pairing each train with its own arrival and departure hides the answer, because what matters is not any single train but how many are standing at the same instant. Split every train into two independent timeline events — an arrival that takes a platform, a departure that frees one — sort them by clock time, and walk them in order. A running counter then IS the number of trains at the station at that moment, and the largest value it ever reaches is the number of platforms needed. Ties matter: an arrival at the same minute as a departure is processed first, because both trains are briefly present.

Details

Animated on: arrivals = [900, 940, 950, 1100, 1500], departures = [910, 1200, 1120, 1130, 1900] — what is the fewest platforms the station can run with so no train ever waits?

Problem:Minimum PlatformsMedium

Chronological sweep of arrivals and departures

step 1 / 13

A 900
[0]
D 910
[1]
A 940
[2]
D 1200
[3]
A 950
[4]
D 1120
[5]
A 1100
[6]
D 1130
[7]
A 1500
[8]
D 1900
[9]

5 trains become 10 timeline events, listed train by train: arrival then departure for train 1, then train 2, and so on. In this order the row jumps back and forth in time (900 then 910 then 940), so counting how many trains are standing at once is impossible yet.

Pseudocode
1FUNCTION minPlatforms(arr, dep)
2  events <- EMPTY LIST
3  FOR i <- 0 TO LENGTH(arr) - 1
4    APPEND (arr[i], +1) TO events
5    APPEND (dep[i], -1) TO events
6  SORT events BY TIME ASCENDING, ARRIVALS BEFORE DEPARTURES
7  platforms <- 0
8  best <- 0
9  FOR EACH (time, delta) IN events
10    platforms <- platforms + delta
11    best <- MAX(best, platforms)
12  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. 5 trains become 10 timeline events, listed train by train: arrival then departure for train 1, then train 2, and so on. In this order the row jumps back and forth in time (900 then 910 then 940), so counting how many trains are standing at once is impossible yet.
  2. Sorted by clock time: A 900, D 910, A 940, A 950, A 1100, D 1120, D 1130, D 1200, A 1500, D 1900. Now the row IS the station's day in order, so walking it left to right replays what actually happens minute by minute. An arrival is placed before a departure at the same minute, since a train pulling in as another pulls out still needs its own platform.
  3. At 900 train 1 pulls in and takes a platform, so 1 train is now standing. That beats every earlier moment, so the answer rises to 1 — the station has never been this full before.
  4. At 910 train 1 leaves and frees a platform, dropping the station to 0. A departure can never raise the peak, so the answer stays 1.
  5. At 940 train 2 pulls in and takes a platform, so 1 train is now standing. The busiest moment so far is still 1, so nothing changes.
  6. At 950 train 3 pulls in and takes a platform, so 2 trains are now standing. That beats every earlier moment, so the answer rises to 2 — the station has never been this full before.
  7. At 1100 train 4 pulls in and takes a platform, so 3 trains are now standing. That beats every earlier moment, so the answer rises to 3 — the station has never been this full before.
  8. At 1120 train 3 leaves and frees a platform, dropping the station to 2. A departure can never raise the peak, so the answer stays 3.
  9. At 1130 train 4 leaves and frees a platform, dropping the station to 1. A departure can never raise the peak, so the answer stays 3.
  10. At 1200 train 2 leaves and frees a platform, dropping the station to 0. A departure can never raise the peak, so the answer stays 3.
  11. At 1500 train 5 pulls in and takes a platform, so 1 train is now standing. The busiest moment so far is still 3, so nothing changes.
  12. At 1900 train 5 leaves and frees a platform, dropping the station to 0. A departure can never raise the peak, so the answer stays 3.
  13. The sweep is over. The fullest the station ever got was 3 trains, at 1100 when train 4 arrived — so 3 platforms are needed, and no fewer, because at that one minute 3 trains are physically present.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Platforms in the editorAll Greedy problemsBack to roadmap