Faangprep Logo
Log inStart free
Browse curriculum

Minimum Platforms

The Minimum Platforms problem asks for the fewest platforms a railway station needs, given the arrival and departure times of all trains, so that no train is kept waiting.

Every train needs a platform to itself for as long as it is in. Nobody has to know which train is on which platform — only how many are in at the same time, which is the largest the count ever gets.

READY

T1

T2

T3

T4

T5

T6

ARRIVE

9:00
9:25
9:50
11:20
11:45
12:30

DEPART

10:10
10:45
11:00
12:15
12:40
13:00

In use

0

Platforms

0

 

6 trains through one station, and the only question is how many are standing there at once.

Next

Sort the arrivals, and sort the departures. Nothing pairs the two lists up.

Timetable

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. When an arrival and a departure share a time, count the arrival first: a train arriving at the same minute another leaves still needs its own platform, which is what the arr[i] ≤ dep[j] comparison below encodes. If your problem treats a departure as freeing the platform at that minute, change it to <.
  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".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Job Sequencing

Next

Introduction

Frequently Asked Questions

How are platforms calculated?

Sort all arrivals and departures. Track a "currently active" count - when a train arrives, increment platforms; when it departs, decrement.

Why sort both arrival and departure?

This allows us to process the timeline linearly and know at any specific time exactly how many trains are at the station.

Maximum vs Concurrent?

The answer is the MAXIMUM value of the "Concurrent Trains" count recorded throughout the entire day.