Faangprep Logo
LoginRegister
Browse Curriculum

Minimum Platforms

Given the arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train is kept waiting.

Minimum Platforms

Ready

See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine you are the station master. A platform is needed for every train currently at the station. If a new train arrives while all platforms are occupied, you need another platform.

To find the minimum platforms required, you just need to know the maximum number of trains present at the station at the same time.

Concept

The Greedy Approach (sorting events):

  1. Treat all arrival and departure times as independent events on a timeline.
  2. Sort these events by time. If an arrival and departure happen at the same time, process the arrival (or departure?) - usually departure first to free up platform immediately, or arrival first if strictly overlapping. Typically, if Arr == Dep, we consider the train still there, or left. Standard problem statement says "departure" frees platform.
  3. Iterate through time:
    • Arrival: platform_needed++
    • Departure: platform_needed--
  4. Track the maximum value of platform_needed reached.

How it Works

  1. Sort: Sort the array of Arrival times and Departure times separately.
  2. Two Pointers: Use pointer i for Arrival and j for Departure.
  3. Iterate: Compare arr[i] and dep[j]:
    • If arr[i] ≤ dep[j]: A train arrived. Incr `platforms`. Update `max`. Incr `i`.
    • If arr[i] > dep[j]: A train left. Decr `platforms`. Incr `j`.
  4. Result: The maximum count recorded.

Step-by-Step Breakdown

Trains: T1[9:00-9:10], T2[9:40-12:00], T3[9:50-11:20]

  1. Sort Arrivals: 900, 940, 950.
  2. Sort Departures: 910, 1120, 1200.
  3. Comparison:
  4. 900 (Arr) ≤ 910 (Dep)? Yes. Plat=1. Max=1. Next Arr (940).
  5. 940 (Arr) ≤ 910 (Dep)? No. (Wait, 940 > 910... strict ordering logic)
  6. Actually compare current Arr vs current Dep pointers.
  7. Arr(940) > Dep(910)? Yes. Train left. Plat=0. Next Dep (1120).
  8. Wait, logic:
    Arr[i] vs Dep[j].
    900 vs 910: Arrive. P=1. i=1.
    940 vs 910: Depart. P=0. j=1. (Logic check: 940 > 910 means departure happened BEFORE next arrival).
  9. Correct trace:
    Events: 900(A), 910(D), 940(A), 950(A), 1120(D), 1200(D).
    900(A): P=1.
    910(D): P=0.
    940(A): P=1.
    950(A): P=2. Max=2.
    ...

When to Use

  • Railway station management.
  • Calculating maximum simultaneous resource usage (e.g., server load, meeting rooms).

When NOT to Use

  • When resources are not identical or interchangeable (e.g., specific track types).

How to Identify

Keywords: "Minimum platforms", "Maximum intersection", "Overlapping intervals".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep